Order of execution within monads

Question

I was learning how to use the State monad and I noticed some odd behavior in terms of the order of execution. Removing the distracting bits that involve using the actual state, say I have the following code:

import Control.Monad
import Control.Monad.State
import Debug.Trace

mainAction :: State Int ()
mainAction = do
    traceM "Starting the main action"
    forM [0..2] (\i -> do
        traceM $ "i is " ++ show i
        forM [0..2] (\j -> do
            traceM $ "j is " ++ show j
            someSubaction i j
        )
    )

Running runState mainAction 1 in ghci produces the following output:

j is 2          
j is 1          
j is 0          
i is 2          
j is 2          
j is 1          
j is 0          
i is 1         
j is 2          
j is 1          
j is 0          
i is 0          
Outside for loop

which seems like the reverse order of execution of what might be expected. I thought that maybe this is a quirk of forM and tried it with sequence which specifically states that it runs its computation sequentially from left to right like so:

mainAction :: State Int ()
mainAction = do
    traceM "Outside for loop"
    sequence $ map handleI [0..2]
    return ()
    where
    handleI i = do
        traceM $ "i is " ++ show i
        sequence $ map (handleJ i) [0..2]
    handleJ i j = do
        traceM $ "j is " ++ show j
        someSubaction i j

However, the sequence version produces the same output. What is the actual logic in terms of the order of execution that is happening here?

Answer 1

Haskell is lazy, which means things are not executed immediately. Things are executed whenever their result is needed – but no sooner. Sometimes code isn't executed at all if its result isn't needed.

If you stick a bunch of trace calls in a pure function, you will see this laziness happening. The first thing that is needed will be executed first, so that's the trace call you see first.

When something says "the computation is run from left to right" what it means is that the result will be the same as if the computation was run from left to right. What actually happens under the hood might be very different.

This is in fact why it's a bad idea to do I/O inside pure functions. As you have discovered, you get "weird" results because the execution order can be pretty much anything that produces the correct result.

Why is this a good idea? When the language doesn't enforce a specific execution order (such as the traditional "top to bottom" order seen in imperative languages) the compiler is free to do a tonne of optimisations, such as for example not executing some code at all because its result isn't needed.

I would recommend you to not think too much about execution order in Haskell. There should be no reason to. Leave that up to the compiler. Think instead about which values you want. Does the function give the correct value? Then it works, regardless of which order it executes things in.

Answer 2

I thought that maybe this is a quirk of forM and tried it with sequence which specifically states that it runs its computation sequentially from left to right like so: [...]

You need to learn to make the following, tricky distinction:

1. The order of evaluation
2. The order of effects (a.k.a. "actions")

What forM, sequence and similar functions promise is that the effects will be ordered from left to right. So for example, the following is guaranteed to print characters in the same order that they occur in the string:

putStrLn :: String -> IO ()
putStrLn str = forM_ str putChar >> putChar '\n'

But that doesn't mean that expressions are evaluated in this left-to-right order. The program has to evaluate enough of the expressions to figure out what the next action is, but that often does not require evaluating everything in every expression involved in earlier actions.

Your example uses the State monad, which bottoms out to pure code, so that accentuates the order issues. The only thing that a traversal functions such as forM promises in this case is that gets inside the actions mapped to the list elements will see the effect of puts for elements to their left in the list.