5

我正在看FoldableHaskell 的课程。其中两个方法fold，foldMap需要一个 Monoid 实例。但是foldr或者foldl没有任何这样的约束。

fold :: Monoid m => t m -> m
foldMap :: Monoid m => (a -> m) -> t a -> m
foldr :: (a -> b -> b) -> b -> t a -> b
foldl :: (b -> a -> b) -> b -> t a -> b

为了foldr/的结果foldl是等价的，它不应该限制给定的折叠函数是关联的吗？有没有同一个列表中 foldr/foldl 的结果不同的例子？

Foldable 实例不应该包装 Monoidal 值吗？还是可折叠更通用？

4

1 回答 1

5

为了foldr/的结果foldl是等价的，它不应该限制给定的折叠函数是关联的吗？是否有任何示例在同一列表中foldr/的结果不同？foldl

是的。如果您传递一个非关联函数（如减法(-)），您绝对会得到不同的结果。正如您正确指出的那样，没有任何 Monoid实例对应于(-).

但这是设计使然。对于并且必须采用关联函数的Foldable实例没有这样的限制。在某些情况下，您可能想用减法之类的方法弃牌。的一个实例对限制可以做什么更感兴趣。具体法律如下：foldrfoldlFoldable ff

foldr f z t = appEndo (foldMap (Endo . f) t ) z
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
fold = foldMap id

-- if f is a Functor
foldMap f = fold . fmap f
foldMap f . fmap g = foldMap (f . g)

你可以在源代码中看到默认情况下对内同态幺半群foldr做了一些聪明的事情：newtype Endo a = Endo (a -> a)

-- | Right-associative fold of a structure.
--
-- @'foldr' f z = 'Prelude.foldr' f z . 'toList'@
foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo #. f) t) z

用可能的非单面f和建立一个单面折叠z。

所以最终回答了“为什么 Monoid 不是必需的？”这个问题。是非常无聊的“因为它更实用，最终没有必要”。

有关更多信息，请参阅开始这一切的论文，Applicative Programming with Effects。

于 2016-06-22T16:58:31.947 回答