Почему я получаю ошибку несоответствия типа?

Question

Вот мой код.

{-# LANGUAGE MultiParamTypeClasses #-} 
{-# LANGUAGE FlexibleInstances #-} 

module StateParser where 
import Control.Monad 
import Control.Applicative 

newtype State s a = State {compute :: s -> (a, s)} 

newtype StateM m s a = StateM {compute_M :: s -> m (a, s)} 

result_s :: a -> State s a 
result_s v = State (\s -> (v ,s)) 

bind_s :: State s a -> (a -> State s b) -> State s b 
bind_s st f = State $ \s -> (\(v, s') -> compute (f v) s') (compute st s) 

result_sm :: (Functor m) => a -> StateM m s a 
result_sm v = StateM (\s -> result_s (v, s)) 

bind_sm :: (Functor m) => StateM m s a -> (a -> StateM m s b) -> StateM m s b 
bind_sm stm f = StateM $ \s -> (tmp s `bind_sm` id) 
    where 
    tmp s = fmap (\(v, s') -> compute_M (f v) s') (compute_M stm s) 

instance Functor (State s) where 
    fmap f st = st >>= (pure . f) 

instance Applicative (State s) where 
    pure = result_s 
    p <*> q = p >>= \f -> 
      q >>= (pure . f) 

instance Monad (State s) where 
    --Explicit return definition only required for code required to be compatible 
    --with GHC versions prior to 7.10. The default implementation for all GHC 
    --versions from 7.10 is 
    return = pure 
    (>>=) = bind_s 

instance Functor f => Functor (StateM f s) where 
    fmap f stm = stm `bind_sm` (result_sm . f) 

instance Applicative f => Applicative (StateM f s) where 
    pure = result_sm 
    p <*> q = p `bind_sm` \f -> 
      q `bind_sm` (pure . f) 

instance Monad m => Monad (StateM m s) where 
    return = pure 
    (>>=) = bind_sm 

При компиляции, я получаю ошибки рассогласования 2 типа:

StateParser.hs:43:29 
    Couldn't match type `m' with `State s1' 
     `m' is a rigid type variable bound by 
      the type signature for result_sm :: Functor m => a -> StateM m s a 
      at StateParser.hs:42:14 
    Expected type: m (a, s) 
     Actual type: State s1 (a, s) 
    ... 
    In the expression: result_s (v, s) 
    In the first argument of `StateM', namely 
     `(\ s -> result_s (v, s))' 

StateParser.hs:46:33: 
    Couldn't match type `m' with `StateM m0 s0' 
     `m' is a rigid type variable bound by 
      the type signature for 
      bind_sm :: Functor m => 
         StateM m s a -> (a -> StateM m s b) -> StateM m s b 
      at StateParser.hs:45:12 
    Expected type: StateM m0 s0 (m (b, s)) 
     Actual type: m (m (b, s)) 
    ... 
    In the first argument of `bind_sm', namely `tmp s' 
    In the expression: (tmp s `bind_sm` id) 

Однако, я очень четко определенные экземпляры Functor класса типов для конструкторов типа State s и StateM f s, которые должны позволить им соответствовать с переменной типа m, связанной Functor в bind_sm и result_sm.

Возможно, есть некоторые аспекты процедур вывода типа Haskell, о которых я не знаю. Кто-нибудь просветит меня?

Answer 1

result_sm v = StateM (\s -> result_s (v, s)) 

Похоже на меня. Функция

\s -> result_s (v, s) 

имеет тип

s -> State s (a,s) 

в то время как StateM ожидает

s -> m (a,s) 

для произвольного m, а не только m ~ State s.

Вы уверены, что вы не хотите что-то вроде:

result_sm :: (Monad m) => a -> StateM m s a 
result_sm v = StateM (\s -> return (v, s)) 

(или аппликативном вариант)?