用列表 monad 迭代

Question

我无法理解如何从其 definition.

派生列表 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

什么都没有 built-in，一切都是您引用的 Monad 实例的简单结果（并且，由于此示例使用 do 表示法，因此如何使用 >>=运算符）：

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)
    ]

这是有效的，因为对于 instance 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 循环。

用列表 monad 迭代

iteration with the list monad

monads

haskell

list