18

我试图理解 Haskell monads，阅读“好奇程序员的 Monads”。我遇到了 List Monad 的例子：

tossDie=[1,2,3,4,5,6]

toss2Dice = do
    n <- tossDie
    m <- tossDie 
    return (n+m)

main = print toss2Dice

我有点理解do块生成为 36 元素列表的方式- 它将每个元素映射为 6 个元素的列表，然后连接这些列表。我不明白的是，从 6 个元素列表到 36 个元素的存在如何改变。显然“我们先绑定再绑定”在这里理解是错误的，但什么是正确的呢？mnnm <- tossDienm

我也不完全清楚如何在do块中应用两个参数函数。我怀疑这是一个curying的例子，但我对它的工作原理有点模糊。

有人可以解释上述两个谜团吗？

4

4 回答 4

14

对于列表（例如tossDie），do符号的作用类似于列表推导式——也就是说，就好像每个变量绑定都是一个嵌套foreach循环。

do-block 表达式：

toss2Dice = do { n <- tossDie; m <- tossDie; return (n+m) }

和这个列表理解做同样的事情：

toss2Dice = [ n+m | n <- tossDie, m <- tossDie ]

结果与以下命令式伪代码相当：

toss2Dice = []
foreach n in tossDie:
    foreach m in tossDie:
        toss2Dice.push_back(n+m)

除了 Haskell 示例是根据需要懒惰地生成结果，而不是急切地一次生成结果。

如果您查看列表的 monad 实例，您可以看到它是如何工作的：

instance Monad [] where
  xs >>= f = concat (map f xs)
  return x = [x]

从块的开头开始do，每个变量绑定都会在块的其余部分创建一个循环：

do { n <- tossDie; m <- tossDie; return (n+m) }
===>   tossDie >>= \n -> do { m <- tossDie; return (n+m) }
===>   concat ( map (\n -> do { m <- tossDie; return (n+m) }) tossDie )

请注意， map函数会遍历 list 中的项目tossDie，并生成结果concat。映射函数是do块的其余部分，因此第一个绑定有效地围绕它创建了一个外循环。

附加绑定创建连续嵌套循环；最后，该return函数从每个计算值中创建一个单例列表，(n+m)以便“绑定”函数>>=（它需要列表）可以正确地连接它们。

于 2013-11-13T19:30:09.450 回答
13

我认为有趣的一点是：

toss2Dice = do
  n <- tossDie
  m <- tossDie 
  return (n+m)

这在某种程度上等同于以下 Python：

def toss2dice():
    for n in tossDie:
        for m in tossDie:
            yield (n+m)

对于 list monad，您可以将<-do 表示法中的绑定箭头 ( ) 视为传统的命令式“foreach”循环。之后的一切

n <- tossDie

属于该 foreach 循环的“循环体”，因此将对tossDie分配给的每个值进行一次评估n。

如果您想要从do符号到实际绑定运算符的脱糖>>=，它看起来像这样：

toss2Dice =
  tossDie >>= (\n ->
    tossDie >>= (\m ->
      return (n+m)
    )
  )

注意“内循环体”如何

(\n ->
  tossDie >>= (\m ->
    return (n+m)
  )
)

将为 中的每个值执行一次tossDie。这几乎等同于嵌套的 Python 循环。

Technical mumbo-jumbo：从绑定箭头获得“foreach”循环的原因与您正在使用的特定 monad 有关。箭头对不同的 monad 有不同的含义，要知道它们对特定 monad 的含义，您必须进行一些调查并弄清楚该 monad 通常是如何工作的。

箭头被去糖化为对绑定运算符的调用>>=，这对不同的 monad 也有不同的作用——这就是绑定箭头<-对不同的 monad 也有不同作用的原因！

在 list monad 的情况下，bind 运算符>>=将一个列表放在左边，一个函数返回一个列表到右边，然后将该函数应用于列表的每个元素。如果我们想以繁琐的方式将列表中的每个元素加倍，我们可以想象这样做

λ> [1, 2, 3, 4] >>= \n -> return (n*2)
[2,4,6,8]

(return是使类型起作用所必需的。>>=期望一个返回列表的函数，并且return对于列表 monad，将值包装在列表中。) 为了说明一个可能更强大的示例，我们可以从想象函数开始

λ> let posneg n = [n, -n]
λ> posneg 5
[5,-5]

然后我们可以写

λ> [1, 2, 3, 4] >>= posneg
[1,-1,2,-2,3,-3,4,-4]

计算-4到4之间的自然数。

单子列表以这种方式工作的原因是绑定运算符的这种特殊行为>>=并使return单子法则成立。monad 法则对我们（也许还有冒险的编译器）很重要，因为它们让我们以我们知道不会破坏任何东西的方式更改代码。

这样做的一个非常可爱的副作用是它使列表非常方便地表示值的不确定性：假设您正在构建一个 OCR thingey，它应该查看图像并将其转换为文本。您可能会遇到可能是 4 或 A 或 H 的字符，但您不确定。通过让 OCR thingey 在 list monad 中工作并返回['A', '4', 'H']您已经涵盖了基础的列表。do实际使用扫描的文本然后使用list monad 的符号变得非常容易和可读。（看起来您正在使用单个值，而实际上您只是在生成所有可能的组合！）

于 2013-11-13T18:57:04.860 回答
4

添加到@kqr 答案：

>>=for list monad 实际上是concatMap一个将元素映射到元素列表并连接列表的函数，但参数翻转：

concatMap' x f = concat (map f x)

或者

concatMap' = flip concatMap

return只是

singleElementList x = [x]

现在我们可以>>=用concatMap'and替换singleElementList：

toss2Dice =
  concatMap' tossDie (\n ->
    concatMap' tossDie (\m ->
      singleElementList (n+m)
    )
  )

现在我们可以用它们的主体替换这两个函数：

toss2Dice =
  concat (map (\n ->
    concat (map (\m ->
      [n+m]
    ) tossDice)
  ) tossDice)

删除多余的换行符：

toss2Dice = concat (map (\n -> concat (map (\m -> [n+m]) tossDice)) tossDice)

或更短concatMap：

toss2Dice = concatMap (\n -> concatMap (\m -> [n+m]) tossDice) tossDice
于 2013-11-13T20:24:18.343 回答
3

遵循nponeccop 的建议，与

for = flip concatMap

你的代码变成

toss2Dice = 
    for {- n in -} tossDie {- call -}
        (\n-> for {- m in -} tossDie {- call -}
                  (\m-> [n+m]))

很明显我们有嵌套的函数，一个在另一个里面；所以内部函数(\m-> [n+m])，在外部函数的参数范围内n，可以访问它（即参数n）。因此，它使用外部函数的参数值，在每次调用内部函数时都相同，但是在相同调用外部函数期间调用了多次。

这可以用命名函数重写，

toss2Dice = 
    for {- each elem in -} tossDie {- call -} g
    where g n = for {- each elem in -} tossDie {- call -} h
                where h m = [n+m]

该函数h是在 内部 g定义的，即在g' 参数的范围内。这就是如何h同时使用两者m，n即使只是m它的论点。

所以实际上我们确实在这里“先绑定n然后绑定m”。以嵌套方式，就是这样。

于 2013-11-13T21:35:41.960 回答