How do you reason about the order of execution of functions in a monadT stack?

Question

General theme: While I find the idea of stacking monads together is very appealing, I am having a lot of trouble picturing how the code is executed, and what are the appropriate orders to run the layers. Below is one example of a stack: Writer, State, State, and Error, in no particular order ( or is there? ).

-----------------------
-- Utility Functions --
-----------------------

type Memory  = Map String Int
type Counter = Int
type Log     = String

tick :: (MonadState Counter m) => m ()
tick = modify (+1) 

record :: (MonadWriter Log m) => Log -> m ()
record msg = tell $ msg ++ "; "

------------------
-- MonadT Stack --
------------------

mStack :: ( MonadTrans t, MonadState Memory m, MonadState Counter (t m), MonadError ErrMsg (t m), MonadWriter Log (t m) ) => t m Int
mStack = do
    tick
    m <- lift get
    let x = fromJust ( M.lookup "x" m ) in x
    record "accessed memory"
    case True of 
        True  -> return 100
        False -> throwError "false"

Please note in mStack, whether an error is thrown or not has nothing to do with any other part of the function.

Now ideally I want the output to look like this:

( Right 100, 1, "accessed memory", fromList [...])

or in general:

( output of errorT, output of stateT Counter, output of writerT, output of StateT Memory )

But I cannot get it to work. Specifically, I tried running the stack as if Error is on the outermost layer:

mem1 = M.fromList [("x",10),("y",5)]
runIdentity $ runWriterT (runStateT (runStateT (runErrorT mStack ) 0 ) mem1 ) ""

But am getting this error message:

  Couldn't match type `Int' with `Map [Char] Int'

---

The above instance aside, in general, when I am calling:

runMonadT_1 ( runMonadT_2 expr param2 ) param1,

are the functions relating to monadT_2 run first, then that output is piped into the functions relating to monadT_1 ? So in other words, as imperative as the code looks in the above function mStack, is the order of execution entirely dependent upon the order in which the monadT are run ( aside from any rigidness in structure introduced by lift ) ?

Answer 1

You would have gotten a more informative type error if you had tried to type your computation using an explicit monad transformer stack:

mStack :: ErrorT String (StateT (Map String Int) (StateT Int Writer)) Int

Had you done that, ghc would have caught the type error earlier. The reason is that you use the following two commands within mStack at the top-most level:

modify (+1)  -- i.e. from `tick`
...
yourMap <- lift get

If you were to give this an explicit stack, then you'd catch the mistake: both modify and lift get are going to target the first StateT layer they encounter, which happens to be the same StateT layer.

modify begins from the ErrorT layer and proceeds downward until it hits the outer StateT layer, and concludes that the outer StateT must be using an Int state. get begins from the outer StateT layer, notices that it's already in a StateT layer and ignores the inner StateT layer entirely, so it concludes that the outer StateT layer must be storing a Map.

ghc then says "What gives? This layer can't be storing both an Int and a Map!", which explains the type error you got. However, because you used type classes instead of a concrete monad transformer stack, there was no way that ghc could know that this was a type error in waiting until you specified a concrete stack.

The solution is simple: just add another lift to your get and it will now target the inner StateT layer like you intended.

I personally prefer to avoid mtl classes entirely and always work with a concrete monad transformer stack using the transformers library alone. It's more verbose because you have to be precise about which layer you want using lift, but it causes fewer headaches down the road.