Haskell — Monad binding evaluation order

Question

I'm having some trouble figuring out /how/ the bind operator would actually bind together the following State monads:

pop :: State [Int] Int
pop = do
        (x:xs) <- get
        put xs
        return x

push :: Int -> State [Int] ()
push x = do 
            xs <- get
            put (x:xs)

doStuff :: State [Int] ()
doStuff = do
            pop
            x <- pop
            push 5
            push x

Take doStuff, which can be desugared to the following:

pop >>= (\_ -> pop >>= (\x -> push 5 >>= (\_ -> push x)))

When this line is evaluated, in what order does the binding actually happen? Since, to actually bind, Haskell needs to get a State monad out of the function on the right of the >>= operator (i.e. the function right operands need to be fully evaluated first), I would've thought that the following would happen:

1. s1 = push 5 >>= (\_ -> push x)
2. s2 = pop >>= (\x -> s1)
3. s3 = pop >>= (\_ -> s2)

Is this the right way to think about it? I feel that I understand monads well, but my biggest problem is in actually visualising what's happening "behind the scenes" and how the data is flowing, so to speak. The do notation gives the illusion that I'm dealing with a bunch of sequential operations, when in fact, there's a whole bunch of nesting and closures.

I feel somewhat like I'm over-thinking things here and further confusing myself as a result.

Answer 1

Starting from

pop >>= (\_ -> pop >>= (\x -> push 5 >>= (\_ -> push x)))

a few functions can be inlined (to show what is happening better). I will start with (>>=), pretending that State is not defined as a transformer or newtype, to keep things simple.

type State s a = s -> (a, s)
m >>= k = \ s -> let (a, s') = m s in k a s'

\ s -> let (a, s') = pop s in
(\ _ -> pop >>= (\ x -> push 5 >>= (\ _ -> push x))) a s'

\ s -> let (_, s') = pop s in
(pop >>= (\ x -> push 5 >>= (\ _ -> push x))) s'

\ s -> let (_, s') = pop s in
let (a, s'') = pop s' in
(\ x -> push 5 >>= (\ _ -> push x)) a s''

\ s -> let (_, s') = pop s in
let (a, s'') = pop s' in
(push 5 >>= (\ _ -> push a)) s''

\ s -> let (_, s') = pop s in
let (a, s'') = pop s' in
let (b, s''') = push 5 s'' in
(\ _ -> push a)) b s'''


\ s -> let (_, s') = pop s in
let (a, s'') = pop s' in
let (_, s''') = push 5 s'' in
push a s'''