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?

score 21 · Accepted Answer · answered Apr 19 '15 at 16:28

21

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.

answered Apr 19 '15 at 16:28

kqr

14,791
3
41
72

Thanks for the detailed explanation! I ran across this issue when trying to translate a very mutation dependent implementation of Smith-Waterman in Java. What would be the best way to translate such code into a language like Haskell? – Arbus Apr 19 '15 at 17:08
2

You mean "evaluate" everywhere you wrote "execute" (as does the OP). – Reid Barton Apr 19 '15 at 18:34
1

@Arbus You can use the `ST`monad to do mutation – jberryman Apr 19 '15 at 19:57
@Arbus Generally you can use the `ST` monad to do mutation, but in the specific case of Smith-Waterman I have to wonder why you're translating it from Java in the first place. – Jeremy List Apr 20 '15 at 02:06
Thanks for the heads up on the `ST`, I am working on it now. I am doing it so that I can do a comparison between a functional implementation and comparing it to an implementation in X10 for a class which is probably why the question itself is a bit convoluted in the first place! – Arbus Apr 20 '15 at 05:16
@ReidBarton I was debating writing "evaluate" instead of "execute" but decided to go with the same word as OP for pedagogical reasons. Accurate observation, nonetheless. :) – kqr Apr 20 '15 at 08:36

Luis Casillas · Answer 2 · 2016-11-03T22:30:19.747

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:

The order of evaluation
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.

Order of execution within monads

2 Answers2

Linked