Search code examples
haskellmonadsstate-monad

Implementing Monad instance for a nested monadic type

As a part of self-learning exercise in Haskell, I am trying to derive a Monad instance for my type. The type is defined as:

newtype ParsePackUnpack f a = ParsePackUnpack
  {
    unparse:: State PackUnpackState (Ap f a)
  }

where Ap f a comes from Data.Monoid. With my type, I'm trying to say that parsing is a stateful operation with the result being any monoid.

So far, I have been successful in implementing Functor and Applicative instances for this 3 level deep type by lifting:

instance Functor f => Functor (ParsePackUnpack f) where
  fmap f ma =
    let f' = fmap f     -- lift (a -> b) to (Ap f a -> Ap f b)
     in ParsePackUnpack $ f' <$> (unparse ma)

instance Applicative f => Applicative (ParsePackUnpack f) where
  pure = ParsePackUnpack . pure . pure

  f <*> ma =
    let f' = liftA2 (<*>) . unparse $ f       -- lift Ap f (a -> b) -> Ap f a -> Ap f b to State s (Ap f a) -> State s (Ap f b)
     in ParsePackUnpack $ f' (unparse ma)     -- Apply to State s (Ap f a)

But I could not derive a Monad instance for my type correctly. After some type-golfing, this is my latest attempt:

instance Monad f => Monad (ParsePackUnpack f) where
  return = ParsePackUnpack . return . return

  ma >>= f = ParsePackUnpack . state $ \st ->
    let (a, s) = runState (unparse ma) st
        res = a >>= fst . flip runState s . unparse . f -- fst ignores state from the result
    in (res, s)

Which I believe is incorrect because I am ignoring the state from res operation.

What is correct way to implement the >>= operation for my type? As this is a learning exercise, I'm trying to avoid Monad transformers. If Monad transformers is the way to go, could you also explain why that is the case?

Solution

  • Monads do not compose as nicely as applicatives. While f (g a) is an applicative whenever f and g are (thus your ability to write the applicative instance), it is not in general a monad when f and g are monads. That's why we need monad transformers but not applicative transformers.

    Here's a related exercise. Forget about using State from the library, let's just work with its representation manually. State s (IO a) unrolls into s -> (IO a, s). To implement bind, you would be given

    f :: s -> (IO a, s)
g :: a -> s -> (IO b, s)

    Can you come up with how to feed the first to the second, passing s through "statefully"?

    bound :: s -> (IO b, s)
bound s0 = ??

    Give it a try. And (spoiler) after you've convinced yourself it's impossible, think about what makes it impossible, and how you would need to modify the types to make it possible. Then use that pattern to define a "StateIO s" monad.