How to design a monadic stack?

Question

How do you design and build your monadic stacks? For the first time I need to build a monadic stack (using transformers) to solve a real world problem, but I'm not thoroughly sure in which order to stack the transformers. As you already know, as long as a computation has kind * -> *, basically anything can play the role of the inner monad in a transformer, thus a couple of questions:

• Should some particular transformer be at the top of the stack (e.g. ReaderT? WriterT?)
• What should drive the design? Intuition? Types? (e.g. shape the stack according to your API's needs)
• Is every stack isomorphic to each other (to a certain extent) or is it likely that, if I build my stack incorrectly I might end up to not being able to use certain underlying monads or to have a big bloated mess of lift . lift . liftIO [...]? My gut feeling would suggest that, if the transformers derive some instances (e.g. MonadReader, MonadIO, etc, like most transformers in mtl do), it shouldn't matter in which order I put the transformers.

I'm interest in hearing from seasoned Haskellers about best practices or rules of thumb.

forever $ print "Thanks!"

A.

Answer 1

It takes experience. One thing to remember is that the monad transformer does not know anything about the monad it is transforming, so the outer one is "bound" by the inner one's behavior. So

StateT s (ListT m) a

is, first and foremost, a nondeterministic computation because of the inner monad. Then, taking nondeterminism as normal, you add state -- i.e. each "branch" of the nondeterminism will have its own state.

Constrast with ListT (StateT s m) a, which is primarily stateful -- i.e. there will only be one state for the whole computation (modulo m), and the computation will act "single threaded" in the state, because that's what State means. The nondeterminism will be on top of that -- so branches will be able to observe state changes of previous failed branches. (In this particular combination, that's really weird, and I've never needed it).

Here is a diagram by Dan Piponi which gives some helpful intuition:

I also find it helpful to expand to the implementation type, to give me a feel for what kind of computation it is. ListT is hard to expand, but you can see it as "nondeterminsm", and StateT is easy to expand. So for the above example, I'd look at

StateT s (ListT m) a =~ s -> ListT m (a,s)

I.e. it takes an incoming state, and returns many outgoing states. This gives you an idea of how it's going to work. A similar approach is to look at the type of the run function that you would need for your stack -- does this match the information you have and the information you need?

Here are some rules of thumb. They are no substitute for taking the time to figure out which one you really need by expanding and by looking, but if you are just looking for "adding features" in a sort of imperative sense, then this might be helpful.

ReaderT, WriterT, and StateT are the most common transformers. First, they all commute with each other, so it is irrelevant what order you put them in (Consider using RWS if you are using all three, though). Also, in practice, I usually want these on the outside, with "richer" transformers like ListT, LogicT, and ContT on the inside.

ErrorT and MaybeT usually go on the outside of the above three; let's look at how MaybeT interacts with StateT:

MaybeT (StateT s m) a =~ StateT s m (Maybe a) =~ s -> m (Maybe a, s)
StateT s (MaybeT m) a =~ s -> MaybeT m (a,s) =~ s -> m (Maybe (a,s))

When MaybeT is on the outside, a state change is observable even if the computation fails. When MaybeT is on the inside, if the computation fails, you don't get a state out, so you have to abort any state changes that happened in the failing computation. Which one of these you want depends on what you are trying to do -- the former, however, corresponds to imperative programmers' intuitions. (Not that that's necessarily something to be strived for)

I hope this gave you an idea of how to think about transformer stacks, so you have more tools to analyze what your stack should look like. If you identify a problem as a monadic computation, getting the monad right is one of the most important decisions to make, and it's not always easy. Take your time and explore the possibilities.

Answer 2

This is quite a broad question. I'm just going to give you some basic ideas to work with.

First of all, I suggest keeping the base monad polymorphic wherever possible. This will allow you to reuse code in both pure and IO settings. This will also make your code more composable. Using the various classes like MonadIO can also help keep your code more polymorphic, which is generally a good thing.

One important thing to note is that the order of your monad transformers actually controls their semantics. My favorite example is combining something like ListT¹ with EitherT for error handling. If you have the ListT on the outside, the entire computation can fail with an error. If you have EitherT on the outside, then each branch can fail separately. So you can actually control the way errors interact with non-determinism just by changing the order of your transformers!

If the monad transformers you're using don't depend on order--e.g. it won't matter much for combining ReaderT and WriterT, I believe--then just play it by ear and go with whatever seems best for your application. This is the sort of choice which will get easier with experience.

¹: ListT from Control.Monad.Trans has some issues, so assume it's ListT done right.