Having difficulty understanding type inference in Haskell

0
votes

In Haskell, we know that if we have some function f with the type signature f :: a -> a, then Haskell can infer the following types:

f "alpha" will have type [Char];

f 1234 will have type Num a => a

f Just will have type a -> Maybe a

and so on.

With reference to the following code,

in the function result_sm :: (Monad m) => a -> State m s a, I would like the type variable m to be inferred to State s. State s is an instance of the Monad typeclass, so why isn't it working?

Also, regarding the instance declaration for Functor (StateM m s), I know that the compiler cannot deduce Monad m from the context Functor m bound by the ghc-inbuilt (natural/un-overridden) type signature for fmap.

Similarly, regarding the instance declaration for Applicative (StateM m s), I know that the compiler also cannot deduce Monad m from the context (Functor (StateM m s), Applicative m) bound by the ghc-inbuilt (natural/un-overridden) type signatures for pure and <*>.

So my second question is as follows: how can I get the compiler to accept m as an instance of Monad typeclass in the above two instance declarations, and any similar instance declarations?

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

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 :: (Monad m) => a -> StateM m s a
result_sm v = StateM (\s -> result_s (v, s))

bind_sm :: (Monad m) => StateM m s a -> (a -> StateM m s b) -> StateM m s b
bind_sm stm f = StateM $ \s -> (tmp s >>= 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 m => Functor (StateM m s) where
  fmap :: (Monad m) => (a -> b) -> StateM m s a -> StateM m s b
  fmap f stm = stm `bind_sm` (result_sm . f)

instance Applicative m => Applicative (StateM m s) where
  pure :: (Monad m) => a -> StateM m s a
  pure = result_sm

  (<*>) :: (Monad m) => StateM m s (a -> b) -> StateM m s a -> StateM m s b
  p <*> q = p `bind_sm` \f ->
            q `bind_sm` (pure . f)

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

And here are the full compiler error messages. Someone (username: Bergi) wanted to see them.

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

StateParser.hs:52:11:
    Could not deduce (Monad m)
    from the context (Functor m)
      bound by the type signature for
                 fmap :: Functor m => (a -> b) -> StateM m s a -> StateM m s b
      at StateParser.hs:52:11-63
    Possible fix:
      add (Monad m) to the context of
        the type signature for
          fmap :: Functor m => (a -> b) -> StateM m s a -> StateM m s b
    When checking that:
        forall (m :: * -> *) s.
        Functor m =>
        forall a b. Monad m => (a -> b) -> StateM m s a -> StateM m s b
      is more polymorphic than:
        forall (m :: * -> *) s.
        Functor m =>
        forall a b. (a -> b) -> StateM m s a -> StateM m s b
    When checking that instance signature for `fmap'
      is more general than its signature in the class
      Instance sig: forall (m :: * -> *) s.
                    Functor m =>
                    forall a b. Monad m => (a -> b) -> StateM m s a -> StateM m s b
         Class sig: forall (m :: * -> *) s.
                    Functor m =>
                    forall a b. (a -> b) -> StateM m s a -> StateM m s b
    In the instance declaration for `Functor (StateM m s)'

StateParser.hs:56:11:
    Could not deduce (Monad m)
    from the context (Functor (StateM m s), Applicative m)
      bound by the type signature for
                 pure :: (Functor (StateM m s), Applicative m) => a -> StateM m s a
      at StateParser.hs:56:11-40
    Possible fix:
      add (Monad m) to the context of
        the type signature for
          pure :: (Functor (StateM m s), Applicative m) => a -> StateM m s a
    When checking that:
        forall (m :: * -> *) s.
        (Functor (StateM m s), Applicative m) =>
        forall a. Monad m => a -> StateM m s a
      is more polymorphic than:
        forall (m :: * -> *) s.
        (Functor (StateM m s), Applicative m) =>
        forall a. a -> StateM m s a
    When checking that instance signature for `pure'
      is more general than its signature in the class
      Instance sig: forall (m :: * -> *) s.
                    (Functor (StateM m s), Applicative m) =>
                    forall a. Monad m => a -> StateM m s a
         Class sig: forall (m :: * -> *) s.
                    (Functor (StateM m s), Applicative m) =>
                    forall a. a -> StateM m s a
    In the instance declaration for `Applicative (StateM m s)'

StateParser.hs:59:12:
    Could not deduce (Monad m)
    from the context (Functor (StateM m s), Applicative m)
      bound by the type signature for
                 (<*>) :: (Functor (StateM m s), Applicative m) =>
                          StateM m s (a -> b) -> StateM m s a -> StateM m s b
      at StateParser.hs:59:12-75
    Possible fix:
      add (Monad m) to the context of
        the type signature for
          (<*>) :: (Functor (StateM m s), Applicative m) =>
                   StateM m s (a -> b) -> StateM m s a -> StateM m s b
    When checking that:
        forall (m :: * -> *) s.
        (Functor (StateM m s), Applicative m) =>
        forall a b.
        Monad m =>
        StateM m s (a -> b) -> StateM m s a -> StateM m s b
      is more polymorphic than:
        forall (m :: * -> *) s.
        (Functor (StateM m s), Applicative m) =>
        forall a b. StateM m s (a -> b) -> StateM m s a -> StateM m s b
    When checking that instance signature for `<*>'
      is more general than its signature in the class
      Instance sig: forall (m :: * -> *) s.
                    (Functor (StateM m s), Applicative m) =>
                    forall a b.
                    Monad m =>
                    StateM m s (a -> b) -> StateM m s a -> StateM m s b
         Class sig: forall (m :: * -> *) s.
                    (Functor (StateM m s), Applicative m) =>
                    forall a b. StateM m s (a -> b) -> StateM m s a -> StateM m s b
    In the instance declaration for `Applicative (StateM m s)'
1
haskelltypesfunctional-programmingmonadstemplate-haskell
What is the compiler error you are getting? – Bergi
I'll add the full error messages above right now. – John
"I would like the type variable m to be inferred" - that's not how it works. Types are inferred a) if they are not given b) to check the given ones for correctness. The compiler error tells you that the type is (non-variable) State s0, but you have given it the variable m. – Bergi
Yes, but m is a type variable, not a type. That's why I included the info and examples at the beginning. I appreciate you taking the time to comment/answer, but to be honest, I don't fully understand what you mean. – John
@chi. Indeed it was, I have reposted the question with additional detail and finally got a good answer, thanks to Bergi and Alec. The other post was nuked nuked into oblivion. – John

1 Answers

4
votes

The compiler did its job. Your code doesn't make sense.

  1. In result_sm, you are trying to construct a StateM m s a with a State s a, which is a type mismatch. What you probably meant to do was 

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

  2. Since bind_sm has the constraint Monad m on it, you need to carry that constraint wherever you use bind_sm, including in the Functor, Applicative, and Monad instances of bind_sm. Therefore, these should read

    instance Monad m => Functor (StateM m s) where ..
instance Monad m => Applicative (StateM m s) where ..
instance Monad m => Monad (StateM m s) where ..