haskell - Haskell — Monad 绑定求值顺序

Question

我在弄清楚 /how/ 绑定运算符实际上将以下 State 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

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

Answer 2

这是正确的思考方式吗？

不。

首先：虽然在 monad 中考虑“首先发生这种情况，然后发生这种情况，然后我们评估这个键盘输入......”显然是正确的IO，但并非所有 monad 都是如此。例如，在 list monad 中，这实际上没有任何意义。一般来说，根本不可能为 Haskell 中的计算分配特定的顺序，这不是定义的行为。

然而，在 monad 中考虑计算顺序总是可能的，而且通常很有帮助，而这个顺序实际上是do符号所暗示的顺序。因此，大多数情况下，考虑脱糖表达实际上并不具有洞察力。但如果你想迈出这一步，我会这样做：

1. pop >>= \_ -> THUNK1

2. THUNK1 ≡>pop >>= \x -> THUNK2

3. { Closure{x}} THUNK2 ≡>push 5 >>= \_ -> THUNK3

4. { Closure{x}} THUNK3 ≡>push x

do这当然更丑陋，但说起来与含糖的表达几乎相同。

Answer 3

评估此行时，绑定实际发生的顺序是什么？

这里的“绑定”没有什么特别之处。脱糖表达式的评估方式与任何其他表达式完全相同（惰性），具体取决于(>>=)您正在使用的特定 monad 的实现。

如果我们正在谈论使用类似的东西runState，给定一个类似的表达式foo >>= (\x -> bar)，最外面的表达式是应用程序(>>=)但我们试图解开 anewtype然后在里面应用函数，所以(>>=)被强制，函数也是如此。

如果我们改为考虑列表 monad，(>>=)则为concatMap. 给定一个类似 的表达式[foo1, foo2] >>= (\x -> [bar1, bar2, x] >>= (\y -> [baz, y]))，take 5在结果上使用显然不会完全计算所有绑定。

---

也就是说，这里有一个重要规则：无论评估在何种程度上x >>= f强制评估x，在像脱糖块这样的大表达式do中，强制将以明显的“顺序”顺​​序发生，原因与“顺序错觉”的原因相同可能的。