Haskell——单子绑定求值顺序

Question

我在弄清楚绑定运算符如何将以下状态单子绑定在一起方面遇到了一些麻烦：

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)

这是正确的思考方式吗？我觉得我很好地理解了单子，但我的最大问题在于实际上“幕后发生了什么”以及数据如何流动，就像说的那样。 do符号给人一种处理一系列操作的假象，而事实上，有许多嵌套和闭包。

我感到自己在过度思考并因此进一步混淆自己。

- Matthew H

---

你应该将 >>= 的定义从状态单子扩展到感受一下会发生什么。没有什么特别的事情，只是普通的求值。 - augustss

评估策略在这里并不重要，因此没有“正确”的思考方式。您可以通过尝试不同的评估方式轻松看到这一点。结果总是相同的。 - Niklas B.

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

- ScootyPuff

Answer 2

这是正确的思考方法吗？

不是的。

首先：虽然在IO单子中“首先发生这个，然后那个，然后我们评估这个键盘输入…”显然是正确的思考方式，但这对于所有单子来说都不是真的。例如，在列表单子中，这根本没有任何意义。一般来说，在Haskell中不可能对计算进行特定排序，这不是定义好的行为。

然而，总是有可能，并且很常见地，在单子中考虑计算顺序非常有帮助，事实上，这个顺序就是do符号建议的顺序。因此，大多数情况下，想解析出表达式并不是真正具有洞察力的。但是如果您希望迈出这一步，那么这是我会做的：

1. pop >>= \_ -> THUNK1 2. THUNK1 ≡> pop >>= \x -> THUNK2 3. {Closure{x}} THUNK2 ≡> push 5 >>= \_ -> THUNK3 4. {Closure{x}} THUNK3 ≡> push x 这当然非常丑陋，但与糖衣表达式相比，基本上是在表达同样的意思。

- leftaroundabout

Answer 3

当这一行被评估时，绑定实际发生的顺序是什么？

这里没有关于"binding"的特殊之处。展开后的表达式以与任何其他表达式完全相同（懒惰）的方式进行评估，并且具体取决于您正在使用的特定单子的(>>=)的实现。

如果我们谈论使用类似于runState的东西，给定像foo >>= (\x -> bar)这样的表达式，最外层的表达式是(>>=)的应用程序，但我们试图解包一个newtype然后应用内部的函数，因此(>>=)会被强制执行，函数也会被强制执行。

如果我们考虑列表单子，(>>=)是concatMap。给定像[foo1, foo2] >>= (\x -> [bar1, bar2, x] >>= (\y -> [baz, y]))这样的表达式，对结果使用take 5显然不会完全计算所有绑定。

尽管如此，这里有一个重要的规则：在评估x >>= f强制评估x的程度，对于像展开后的do块这样的大型表达式，强制将按照表面上的“顺序”发生，原因与“顺序幻觉”相同。

- C. A. McCann