Haskell中State类型的Functor与Applicative实例定义错误排查

我正在尝试用Haskell编写有状态代码，学习Monad、Functor相关内容时遇到阻碍。我编写了包含自定义State类型及其实例的代码，但运行时出现错误，具体如下：

我的代码 #

import Control.Monad

data State s a = State (s -> (a,s))

runState (State f) s = f s

put :: s -> State s ()
put state = State (\oldState -> ((), state))

get :: State s s
get = State (\state -> (state,state))

modify :: (s -> s) -> State s ()
modify f = State (\state -> ((), f state))

-- 以下3行报错：
instance Functor State where
  fmap f (State s) = State (f x)
  
-- 以下3行报错：
instance Applicative State where
  pure = return
  (<*>) = ap

instance Monad (State s) where
  return x = State (\s -> (x,s))
  
  op >>= f = State h
    where h state0 = let (val,state1) = runState op state0
                         op2 = f val
                     in runState op2 state1
                     
add :: Int -> State Int ()
add i = do old <- get
           put (old+i)
           
main = do
  print(runState (add 1 >> add 3 >> add 5 >> add 6) 0)

错误信息 #

question1.hs:16:18: error:
    * Expecting one more argument to `State'
      Expected kind `* -> *', but `State' has kind `* -> * -> *'
    * In the first argument of `Functor', namely `State'
      In the instance declaration for `Functor State'
   |
16 | instance Functor State where
   |                  ^^^^^

question1.hs:19:22: error:
    * Expecting one more argument to `State'
      Expected kind `* -> *', but `State' has kind `* -> * -> *'
    * In the first argument of `Applicative', namely `State'
      In the instance declaration for `Applicative State'
   |
19 | instance Applicative State where
                          ^^^^^

问题 #

请问我忽略了什么问题？

核心问题：类型构造器的种类不匹配 #

Functor和Applicative类型类要求实例是仅接受单个类型参数的构造器（种类为* -> *），但你的State是接受两个类型参数的构造器（种类为* -> * -> *）：State s a中s是状态类型，a是计算结果类型。

你在Monad实例里已经做对了：instance Monad (State s) where——这里State s是部分应用后的构造器，仅剩下一个类型参数a，符合Monad的种类要求。同理，Functor和Applicative的实例也需要采用这种部分应用的写法。

修复步骤 #

1. 修正Functor实例
   原代码的fmap实现逻辑也错误，需要正确处理状态传递。正确实现如下：

   instance Functor (State s) where
     fmap f (State sa) = State (\s -> let (a, s') = sa s in (f a, s'))
   

   逻辑说明：取出原状态函数的结果a，用f映射得到新结果，同时保留状态的更新值s'。

2. 修正Applicative实例
   同样需要指定部分应用的State s作为实例，若想复用Monad的实现，可以保留pure = return和<*> = ap，但必须修正实例头：

   instance Applicative (State s) where
     pure = return
     (<*>) = ap
   

   也可以写出完整的实现逻辑：

   instance Applicative (State s) where
     pure x = State (\s -> (x, s))
     State sf <*> State sa = State (\s -> let (f, s') = sf s; (a, s'') = sa s' in (f a, s''))
   

完整修复后的代码 #

import Control.Monad

data State s a = State (s -> (a,s))

runState (State f) s = f s

put :: s -> State s ()
put state = State (\oldState -> ((), state))

get :: State s s
get = State (\state -> (state,state))

modify :: (s -> s) -> State s ()
modify f = State (\state -> ((), f state))

instance Functor (State s) where
  fmap f (State sa) = State (\s -> let (a, s') = sa s in (f a, s'))
  
instance Applicative (State s) where
  pure = return
  (<*>) = ap

instance Monad (State s) where
  return x = State (\s -> (x,s))
  
  op >>= f = State h
    where h state0 = let (val,state1) = runState op state0
                         op2 = f val
                     in runState op2 state1
                     
add :: Int -> State Int ()
add i = do old <- get
           put (old+i)
           
main = do
  print(runState (add 1 >> add 3 >> add 5 >> add 6) 0)

运行结果 #

执行后会输出((),15)，符合预期：初始状态为0，依次累加1、3、5、6后最终状态为15，计算结果为单元值()。

内容的提问来源于stack exchange，提问作者coderodde