4

我知道如何使用仅使用“绑定”操作的 list monad来执行与 Scheme（或 Python）map和函数等效的操作。filter

这里有一些 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组合的函数。该函数使用提供的二元函数组合列表的前两个元素，然后将结果组合到下一个元素，依此类推。计算值列表的总和或乘积的常见用途。这里有一些 Python 来说明：mapfilterreduce

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

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

如果可能，请在回答时限制/避免使用语法糖（即：doHaskell 中的符号或 Scala 中的序列理解）。

4

2 回答 2

4

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

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

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

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

于 2012-06-08T22:43:49.697 回答
3

如果 bind 不能自行执行此操作，那么执行此操作的最“单子”方式是什么？

虽然@sepp2k 给出的答案是正确的，但有一种方法可以reduce对列表进行类似操作，但使用 product 或“writer” monad 和对应于将product monad分布在列表 functor上的操作。

定义是：

import Control.Monad.Writer.Lazy
import Data.Monoid

reduce :: Monoid a => [a] -> a
reduce xs = snd . runWriter . sequence $ map tell xs

让我打开包装：

  • Writermonad 有一个数据类型Writer w a，它基本上是一个值a和“写入”值的元组（乘积） w。写入值的类型w必须是monoid，其中 monad 的绑定操作Writer定义如下：

        (w, a) >>= f = let (w', b) = f a in (mappend w w', b)

    即获取传入的写入值和结果写入值，并使用幺半群的二元运算将它们组合起来。

  • 该tell操作写入一个值，tell :: w -> Writer w ()。因此map tell具有类型[a] -> [Writer a ()]，即一元值列表，其中原始列表的每个元素都已“写入”到单子中。

  • sequence :: Monad m => [m a] -> m [a]对应于列表和 monad 之间的分配法则，即在列表类型上分配 monad 类型；sequence可以根据绑定定义为：

    sequence [] = return []
sequnece (x:xs) = x >>= (\x' -> (sequence xs) >>= (\xs' -> return $ x':xs'))

    （实际上是在Preludeusesfoldr中的实现，是类归约用法的线索）

    因此，sequence $ map tell xs有类型Writer a [()]

  • 该runWriter操作解包Writer类型 ,runWriter :: Writer w a -> (a, w)在这里组成snd以投影出累积值。

s列表的一个示例用法Int是使用 monoid 实例：

  instance Monoid Int where
              mappend = (+)
              mempty = 0

然后：

  > reduce ([1,2,3,4]::[Int])
  10
于 2012-06-09T21:39:28.503 回答