Haskell/Solutions/Monad transformers

Lifting

1.

liftM can be defined in terms of the Monad methods, return and (>>=). These are not enough for defining lift, as how a value in the inner monad should be with the base monad and the transformer depends on what the transformer is like. In particular, the differences between the types wrapped by the transformers, as illustrated in the A plethora of transformers section, make a generic implementation impossible.

2.

newtype IdentityT m a = IdentityT { runIdentityT :: m a }

instance Monad m => Monad (IdentityT m) where
    return x = IdentityT (return x)
    (IdentityT m) >>= k = IdentityT $ m >>= runIdentityT . k

instance MonadTrans IdentityT where
    lift = IdentityT

Implementing transformers

1.

state :: MonadState s m => (s -> (a, s)) -> m a
state f = do
    s <- get
    let (x, s') = f s
    put s'
    return x

2.

They are not equivalent. Specialising the type of runMaybeT to work with MaybeT (State s), we get:

-- runMaybeT :: MaybeT m a -> m (Maybe a)
MaybeT (State s) a -> State s (Maybe a)

Doing the same for runStateT and StateT s Maybe, we obtain:

-- runStateT :: StateT s m a -> s -> m (a, s)
StateT s Maybe a -> s -> Maybe (a, s)

In the first case, we get a State computation that returns a Maybe a. In the second, we get a function which, from an initial state of type s, might give back a result and a new state or not, as the result type is Maybe (a, s). A Nothing amidst a MaybeT (State s) destroys merely the returned result, while in a StateT s Maybe it destroys the final state as well. This comparison can illustrate some general remarks:

In general, the order in which monads are stacked matters.
When a composed monad is unwrapped, the effect of the inner monad has priority over the one of the base monad.
Failure-handling layers such as MaybeT and ExceptT usually go on the top of transformer stacks, so that the effects of the other involved monads are preserved in case of failure.