Haskell - Monad绑定评估顺序

Question

我在搞清楚/如何/绑定运算符实际绑定以下状态monad时遇到了一些麻烦:

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

拿doStuff,可以脱了以下:

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

评估此行时,绑定实际发生的顺序是什么？因为,为了实际绑定,Haskell需要从>>=操作符右侧的函数中获取State monad (即函数右操作数需要首先被完全评估),我会认为会发生以下情况:

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

这是考虑它的正确方法吗？我觉得我很了解monad,但我最大的问题在于实际可视化"幕后"发生的事情以及数据如何流动,可以这么说.该do符号给出了我处理了一堆顺序操作的,而事实上,有一大堆的嵌套和关闭的错觉.

我觉得我有点过于思考这里的事情,结果让自己更加困惑.

Answer 1

从...开始

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

可以内联一些函数(以显示更好的情况).我将开始(>>=)假装State未定义为变换器或新类型,以保持简单.

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'''