Haskell — Monad 绑定(bind)评估顺序

Question

我在弄清楚绑定(bind)运算符如何实际将以下状态单子(monad)绑定(bind)在一起时遇到了一些麻烦:

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

当评估该行时，绑定(bind)实际发生的顺序是什么？因为，要实际绑定(bind)，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'''