为什么 Monoid 不是 foldr/foldl 的要求？

Question

我正在查看 Haskell 中的 Foldable class。 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 值吗？还是Foldable更通用？

Answer 1

For the results of foldr/foldl to be equivalent, shouldn't it restrict the given folding function to be associative? Are there any examples where the results of foldr/foldl are different on the same list?

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

但这是设计使然。 Foldable 实例没有这样的限制，即 foldr 和 foldl 必须采用关联函数。在某些情况下，您可能想要弃牌，例如减法。 Foldable f 的实例对限制 f 可以做什么更感兴趣。具体的法律是：

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.

构建一个幺半群折叠

所以最终问题"Why is Monoid not a requirement?"的答案是非常无聊的"because it is more practical and, in the end, not necessary."

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

为什么 Monoid 不是 foldr/foldl 的要求？

Why Monoid is not a requirement for foldr/foldl?

haskell

fold

monoids

foldable