Haskell — Monad binding evaluation order
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 (ie the function right operands need to be fully evaluated first), I would've thought that the following would happen:
push 5 >>= (_ -> push x) pop >>= (x -> s1) 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.
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'''
Is this the right way to think about it?
No.
First of all: while it is obviously correct to think of "first this happens, than that, then we evaluate this keyboard input..." in the IO monad, this isn't true for all monads. For instance, in the list monad this doesn't really make any sense. In general, it's not possible to assign a particular order to calculations in Haskell at all, it's not defined behaviour.
Yet, it is always possible, and very often helpful, to think of an order of computations in a monad, and this order is in fact the one suggested by the do notation. So, most of the time it isn't actually insightful to think about the desugared expression. But if you wish to make that step, here's how I'd do it:
pop >>= _ -> THUNK1
THUNK1 ≡> pop >>= x -> THUNK2
{ Closure{x} } THUNK2 ≡> push 5 >>= _ -> THUNK3
{ Closure{x} } THUNK3 ≡> push x
Which is of course grotesquely more ugly, but says pretty much the same as the sugared do expression.
When this line is evaluated, in what order does the binding actually happen?
There's nothing special about "binding" here. The desugared expression is evaluated in exactly the same (lazy) way any other expression would be, and the specifics depend on the implementation of (>>=) for the particular monad you're working with.
If we're talking about using something like runState , given an expression like foo >>= (x -> bar) , the outermost expression is the application of (>>=) but we're trying to unwrap a newtype and then apply the function inside, so the (>>=) gets forced, as does the function.
If we consider instead the list monad, (>>=) is concatMap . Given an expression like [foo1, foo2] >>= (x -> [bar1, bar2, x] >>= (y -> [baz, y])) , using take 5 on the result is clearly not going to fully compute all the binds.
That said, there is one important rule here: To whatever extent evaluating x >>= f forces the evaluation of x , in a large expression like a desugared do block the forcing will occur in the apparent "sequential" order, for the same reason that the "sequential illusion" is possible.
上一篇: Monad法则解释