Abstracting monad composition as a transformer

Question

Sorry if the question seems a bit trivial... it is not for me. I have happily composed the following monad:

type SB i a = ReaderT ( AlgRO i ) (State ( AlgState i ) ) a

which is, well, a well behaved monad. ReaderT is a monad transformer and State is the State monad, and AlgRO and AlgState are datatypes parametrized in i for mutable and read-only state, respectively. Now, if I want to make of that a neat monad transformer with newtype, something like this:

newtype SbT m i a = SbT {
    runSbT:: m ( SB i a )
}

how should I proceed? I can not even manage to put together the bind method (of Monad typeclass), much less "lift" (of MonadTrans)... I guess that automatic derivation could help, but I want to understand how it works in this case.

Thanks in advance.

Answer 1

I don't think that definition for SbT is what you want. That defines functor composition, and assuming the m parameter is a Functor or Applicative, this should preserve those properties. But composition like that does not, in general, create a new monad out of two others. See this question for more on that subject.

So, how do you create the monad transformer you want, then? While monads don't compose directly, monad transformers can be composed. So to build a new transformer out of existing ones, you essentially just want to give a name to that composition. This differs from the newtype you have because there you're applying the m directly, instead of passing it in to the transformer stack.

One thing to keep in mind about defining monad transformers is that they necessarily work "backwards" in certain ways--when you apply a composite transformer to a monad, the "innermost" transformer gets the first crack at it, and the transformed monad it produces is what the next transformer out gets to work with, &c. Note that this isn't any different from the order you get when applying a composed function to an argument, e.g. (f . g . h) x gives the argument to h first, even though f is the "first" function in the composition.

Okay, so your composite transformer needs to take the monad it's applied to and pass it to the innermost transformer, which is, uhm.... oops, turns out that SB is already applied to a monad. No wonder this wasn't working. We'll need to remove that, first. Where is it? Not State--we could remove that, but we don't want to, because it's part of what you want. Hmm, but wait--what is State defined as, again? Oh yeah:

type State s = StateT s Identity

Aha, there we go. Let's get that Identity out of there. We go from your current definition:

type SB i a = ReaderT ( AlgRO i ) (State ( AlgState i ) ) a

To the equivalent form:

type SB i a = ReaderT ( AlgRO i ) ( StateT ( AlgState i ) Identity ) a

Then we kick the lazy bum out:

type SB' i m a = ReaderT ( AlgRO i ) ( StateT ( AlgState i ) m ) a
type SB i a = SB' i Identity a

But now SB' looks suspiciously like a monad transformer definition, and with good reason, because it is. So we recreate the newtype wrapper, and toss a few instances out there:

newtype SbT i m a = SbT { getSB :: ReaderT ( AlgRO i ) ( StateT ( AlgState i ) m ) a }

instance (Functor m) => Functor (SbT i m) where
    fmap f (SbT sb) = SbT (fmap f sb)

instance (Monad m) => Monad (SbT i m) where
    return x = SbT (return x)
    SbT m >>= k = SbT (m >>= (getSB . k))

instance MonadTrans (SbT i) where
    lift = SbT . lift . lift

runSbT :: SbT i m a -> AlgRO i -> AlgState i -> m (a, AlgState t)
runSbT (SbT m) e s = runStateT (runReaderT m e) s

A couple things to take note of: The runSbT function here is not the field accessor, but rather a composed "run" function for each transformer in the stack that we know of. Similarly, the lift function has to lift once for the two inner transformers, then add the final newtype wrapper. Both of these make it work as a single monad transformer, hiding the fact that it's actually a composite.

If you'd like, it should be straightforward to write instances for MonadReader and MonadState as well, by lifting the instances for the composed transformers.