使用列表 monad 进行迭代

Question

我无法理解列表 monad 的迭代行为如何从其定义导出。

instance Monad [] where
  m >>= f  = concatMap f m
  return x = [x]
  fail s   = []

我读过的讨论似乎忽略了 >>= 如何创建控制结构的问题，正如 do 表示法最清楚地显示的那样：

allEvenOdds :: Int -> [(Int,Int)]
allEvenOdds n = do
  evenValue <- [2,4 .. n]               
  oddValue <- [1,3 .. n]                
  return (evenValue,oddValue)

这是否内置于Haskell，我假设 IO monad 与实际 i/o 的接口的方式是？

Answer 1

没有任何内置内容，一切都是您引用的 Monad 实例的简单结果（并且，由于此示例使用 do 表示法，因此它如何脱糖以使用 >>=< /code> 运算符）：

allEvenOdds n = do
  evenValue <- [2,4 .. n]               
  oddValue <- [1,3 .. n]                
  return (evenValue,oddValue)

-- desugaring the do notation
allEvenOdds n =
  [2,4 .. n] >>= \evenValue ->
  [1,3 .. n] >>= \oddValue ->
  return (evenValue, oddValue)

-- using the list instance of Monad to replace >>= and return
allEvenOdds n =
  concatMap (\evenValue ->
    concatMap (\oddValue -> [(evenvalue, oddValue)]) [1,3 .. n]
  ) [2,4 .. n]

您希望可以轻松地看到它“迭代”两个列表，并生成所有对（偶数、奇数）的列表，并从两个列表中获取值。

在较高的层次上，我们可以说列表 monad 导致迭代，因为 concatMap 与 map 一样，为列表的每个元素执行给定的函数，因此它隐式地执行迭代列表。

Answer 2

Monad 类型类模型的列表实例非确定性：您可以将每个 var <- someList 视为 for像 Python 中一样循环。

do 表示法被脱糖为 [2,4 .. n] >>= (\evenValue -> [1, 3 .. n] >>= (\ oddValue -> return (evenValue, oddValue)))，因此这相当于 Python 中的内容，例如：

    result = []
    for evenValue in range(2, n, 2):
        for oddValue in range(1, n, 2):
            result.append((evenValue, oddValue))

或者使用列表理解：

    result = [
        (evenValue, oddValue)
        for evenValue in range(2, n, 2)
        for oddValue in range(1, n, 2)
    ]

这对于实例 Monad [] 有效，表达式 [2,4 .. n] >>= (\evenValue -> [1, 3 .. n] >>= (\oddValue -> return (evenValue, oddValue)) ) 因此等价于：

concatMap (\evenValue -> [1, 3 .. n] >>= (\oddValue -> return (evenValue, oddValue))) [2,4 .. n]

因此：

concatMap (\evenValue -> concatMap (\oddValue -> [(evenValue, oddValue)]) [1, 3 .. n]) [2,4 .. n]

但是 do 表示法并不是“硬连线”到 IO：IO 只是一个实例的Monad 的实现方式是一个 IO 操作将在第二个操作之前运行。对于列表，它的实现方式与跨越 Python for 循环的方式相同。