绑定运算符如何被多次调用

Question

首先，如果我没有问正确的问题，我想道歉。我意识到我不太理解 Monad 和绑定运算符的一些基本概念，这使得我很难提出我的问题。我很难理解以下代码如何创建元组列表。

ordPairs :: Ord a => [a] -> [(a, a)]
ordPairs xs =
   xs >>= \x1 ->
   xs >>= \x2 ->
   if x1 < x2 then [(x1, x2)] else []

main = print $ ordPairs [1, 2, 4, 6, 7, 8, 3, 4, 5, 6, 2, 9, 7, 8, 45, 4]

我理解类型声明声明它返回一个 tuples 列表[(a, a)]。我不明白的是这段代码是如何“循环”列表中的每个项目的？作为初学者来看，它看起来好像只向前传递了第一个和第二个项目x1 and x2，然后以if then else表达式结束。这段代码是否被脱糖为多次迭代并在幕后构建列表？我想我要问的是这段代码如何迭代列表中的每个项目并在最后构建一个元组列表？

Answer 1

它可能有助于理解“括号在哪里”。定义的右侧ordPairs解析如下：

xs >>= (\x1 -> xs >>= (\x2 -> if x1 < x2 then [(x1, x2)] else []))

正如您在这里所看到的，该if-then-else表达式并不是独立的，它实际上是一个匿名函数的主体：

\x2 -> if x1 < x2 then [(x1, x2)] else []

显然，可以针对不同的 值多次调用它x2。是什么调用了它？嗯，>>=当然是第二个操作员。“外”循环的工作原理类似，第一个>>=运算符多次调用另一个匿名函数：

\x1 -> xs >>= (\x2 -> ...)

对于此示例，您可以将>>=运算符替换为您自己的自定义bind函数。请注意，这只是一个简单的函数。没有进行特殊的脱糖或秘密迭代。该函数本身使用递归进行迭代：

bind :: [a] -> (a -> [b]) -> [b]
bind (x:xs) f = f x ++ bind xs f
bind [] _ = []

如果你愿意的话，你也可以bind这样写：

bind xs f = concatMap f xs
-- or even `bind = flip concatMap`, as per @WillemVanOnsem's comment

或者作为列表理解。

bind xs f = [y | x <- xs, y <- f x]

最后一个是>>=列表 monad 运算符的实际定义。请参阅GHC/Base.hs。

对于任何这些定义，以下内容都将像原始定义一样工作：

bind :: [a] -> (a -> [b]) -> [b]
bind (x:xs) f = f x ++ bind xs f
bind [] _ = []

ordPairs :: Ord a => [a] -> [(a, a)]
ordPairs xs =
   xs `bind` \x1 ->
   xs `bind` \x2 ->
   if x1 < x2 then [(x1, x2)] else []

main = print $ ordPairs [1,2,4,6,7,8,4,5,6,2,9,7,8,45,4]