这个 do 块是如何工作的？

Question

我几周前刚开始学习Haskell，看到了这个：

moves = do
    f <- [(+), subtract]
    g <- [(+), subtract]
    (x, y) <- [(1, 2), (2, 1)]
    [f x *** g y]

我以前没见过以 list 结尾的 do 代码块，这是解决骑士巡游问题的一部分。有人能解释一下它的工作原理吗？

- tgys

---

这段代码相当于 moves = [f x *** g y | f <- [(+), subtract], g <- [(+), subtract], (x, y) <- [(1, 2), (2, 1)]]。 - Johannes Kuhn

在列表单子中，[x] = return x。 - felix-eku

Answer 1

您需要将符号写成解释性的形式。首先，从类型开始：

import Control.Arrow

moves :: [(Integer, Integer) -> (Integer, Integer)]
moves = do
    f <- [(+), subtract]
    g <- [(+), subtract]
    (x, y) <- [(1, 2), (2, 1)]
    [f x *** g y]

所以我们在 []（列表）单子中。

查找 Monad [] 的定义：

instance  Monad []  where
    m >>= k             = foldr ((++) . k) [] m
    m >> k              = foldr ((++) . (\ _ -> k)) [] m
    return x            = [x]

将do表示法翻译为bind和return：

moves =
    [(+), subtract] >>= \f ->
    [(+), subtract] >>= \g ->
    [(1, 2), (2, 1)] >>= \(x,y) ->
    [f x *** g y]

然后，最后，通过定义重写绑定：

通过在列表上使用return。

moves =
    [(+), subtract] >>= \f ->
    [(+), subtract] >>= \g ->
    [(1, 2), (2, 1)] >>= \(x,y) ->
    return (f x *** g y)

>>= 的定义

moves =
    foldr ((++) . (\f ->

            [(+), subtract] >>= \g ->
            [(1, 2), (2, 1)] >>= \(x,y) ->
            return (f x *** g y)

            )) [] [(+), subtract]

Definition of >>=

moves =
    foldr ((++) . (\f ->
        foldr ((++) . (\g ->
                [(1, 2), (2, 1)] >>= \(x,y) ->
                return (f x *** g y))
                ) [] [(+), subtract]
            )) [] [(+), subtract]

Definition of >>=

moves =
    foldr ((++) . (\f ->
        foldr ((++) . (\g ->
            foldr ((++) . (\(x,y) -> return (f x *** g y))
                    ) [] [(1, 2), (2, 1)]
                )) [] [(+), subtract]
            )) [] [(+), subtract]

撤销返回操作：

moves =
    foldr ((++) . (\f ->
        foldr ((++) . (\g ->
            foldr ((++) . (\(x,y) -> [f x *** g y])
                    ) [] [(1, 2), (2, 1)]
                )) [] [(+), subtract]
            )) [] [(+), subtract]

因此，您可以看到这是两个元素列表上的嵌套折叠。展开折叠留给读者练习 :)

- Don Stewart

---

我已经知道在列表单子的do-comprehension中发生了什么，但是我发现使用foldr展开后的版本难以理解。我不明白它如何帮助那些不知道发生了什么的人。 - amalloy

我不会期望一个初学者理解(++) . (\f -> ...)，最多也只会引发这样的问题：“为什么这不会触发类型错误？” - chi

如果使用concatMap f而不是foldr ((++) . f) []可能会更容易理解。 - David Young