functional-programming - "bind"可以对 List monad 进行减少吗？

Question

我知道如何做相当于 Scheme(或 Python)的 map和 filter仅使用“绑定(bind)”操作的列表单子(monad)函数。

这里有一些 Scala 来说明:

scala> // map
scala> List(1,2,3,4,5,6).flatMap {x => List(x * x)}                        
res20: List[Int] = List(1, 4, 9, 16, 25, 36)

scala> // filter    
scala> List(1,2,3,4,5,6).flatMap {x => if (x % 2 == 0) List() else List(x)}
res21: List[Int] = List(1, 3, 5)

在 Haskell 中也是一样的:

Prelude> -- map
Prelude> [1, 2, 3, 4, 5, 6] >>= (\x -> [x * x])
[1,4,9,16,25,36]

Prelude> -- filter
Prelude> [1, 2, 3, 4, 5, 6] >>= (\x -> if (mod x 2 == 0) then [] else [x])
[1,3,5]

Scheme 和 Python 也有 reduce通常与 map 组合在一起的函数和 filter . reduce函数使用提供的二元函数组合列表的前两个元素，然后将结果组合到下一个元素，依此类推。计算值列表的总和或乘积的常见用途。这里有一些 Python 来说明:

>>> reduce(lambda x, y: x + y, [1,2,3,4,5,6])
21
>>> (((((1+2)+3)+4)+5)+6)
21

有什么方法可以做到reduce仅在列表单子(monad)上使用绑定(bind)操作？如果 bind 不能自行执行此操作，那么执行此操作的最“单子(monad)”方式是什么？

如果可能，请在回答时限制/避免使用语法糖(即:Haskell 中的 do 符号或 Scala 中的序列理解)。

Answer 1

绑定(bind)操作的定义属性之一是结果仍然在 monad¹“内部”。因此，当您对列表执行绑定(bind)时，结果将再次成为列表。由于reduce 操作² 通常会产生列表以外的内容，因此不能用绑定(bind)操作来表示。

除此之外，列表上的绑定(bind)操作(即 concatMap/flatMap)一次只查看一个元素，并且无法重用前面步骤的结果。因此，即使我们可以将结果包装在单元素列表中，也无法仅使用 monad 操作来做到这一点。

¹因此，如果您的类型允许您对其执行除由 monad 类型类定义的操作之外的任何操作，则您永远无法“突破” monad。这就是使 IO monad 起作用的原因。

² 顺便说一句，在 Haskell 和 Scala 中称为 fold。