Error in Monad instance definition for MaybeT

Learn
#1

Hi all,

I am trying to implement a Monad instance for the MaybeT monad transformer (I am learning Haskell and I am following the exercises of Haskell programming from first principles):

newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }

This definition compiles:

instance (Monad m) => Monad (MaybeT m) where
  return = pure
  (MaybeT ma) >>= f = MaybeT $ do
    -- ma :: m (Maybe a)
    --  v :: Maybe a
    v <- ma
    case v of
      Nothing -> return Nothing
      Just y ->
        -- y :: a
        -- f :: a -> MaybeT m b
        -- f y :: MaybeT m b
        -- runMaybeT (f y) :: m (Maybe b)
        runMaybeT $ f y

whereas this one gives an error:

instance (Monad m) => Monad (MaybeT m) where
  return = pure
  (MaybeT ma) >>= f = do
    -- ma :: m (Maybe a)
    --  v :: Maybe a
    v <- ma -- ERROR !!!  Couldn't match type ‘m’ with ‘MaybeT m’
    case v of
      Nothing -> MaybeT $ return Nothing
      Just y ->
        -- y :: a
        -- f :: a -> MaybeT m b
        -- f y :: MaybeT m b
        f y

Here is the compiler output:

    • Couldn't match type ‘m’ with ‘MaybeT m’
      Expected: MaybeT m (Maybe a)
        Actual: m (Maybe a)
      ‘m’ is a rigid type variable bound by
        the instance declaration
        at app/Main.hs:183:10-38
    • In a stmt of a 'do' block: v <- ma
      In the expression:
        do v <- ma
           case v of
             Nothing -> MaybeT $ return Nothing
             Just y -> f y
      In an equation for ‘>>=’:
          (MaybeT ma) >>= f
            = do v <- ma
                 case v of
                   Nothing -> MaybeT $ return Nothing
                   Just y -> f y
    • Relevant bindings include
        f :: a -> MaybeT m b (bound at app/Main.hs:185:19)
        ma :: m (Maybe a) (bound at app/Main.hs:185:11)
        (>>=) :: MaybeT m a -> (a -> MaybeT m b) -> MaybeT m b
          (bound at app/Main.hs:185:15)

Why is v <- ma expecting a MaybeT m (Maybe a) instead of m (Maybe a) as ma is in the second implementation?

Thank you!

#2

As you probably know, do-notation is just sugar for using the basic monad operators.

  do
    v <- ma
    case v of
      Nothing -> MaybeT $ return Nothing
      Just y -> f y

is just another way to write

  ma >>= \v ->
    case v of
      Nothing -> MaybeT $ return Nothing
      Just y -> f y

So to answer your question, look to the type of (>>=). Whatever monad m you’re working with, (>>=) has type m a -> (a -> m b) -> m b. Note that m occurs three times in this type, and all of the ms have to refer to the same type constructor.

ma has to have type m (Maybe a), because you’re getting it from inside the MaybeT constructor. But the lambda to the right of the >>= returns something of type MaybeT m b. The compiler is complaining because it has no reason to believe that m is the same type constructor as MaybeT m, which is what would have to be the case for the use of >>= to type check.

5 Likes
#3

Thank you very much!

2 Likes