haskell - 我如何理解可折叠实例的法律？

在描述Data.Foldable的页面上，它说:
可折叠实例应满足以下法律:

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

请帮助我了解上述法律的运作方式。什么是Endo . f？

最佳答案

Endo 是“组成下的内同态的mono态”。 appEndo是此类型的字段。

newtype Endo a = Endo { appEndo :: a -> a }

-- i.e.
Endo :: (a -> a) -> Endo a
appEndo :: Endo a -> (a -> a)

您可以将“endomorphism”视为输入和输出类型相同的函数的技术上正确的术语(a -> a)。
Endo是Monoid的一个实例，具有以下组成:

instance Monoid (Endo a) where
        mempty = Endo id
        Endo f `mappend` Endo g = Endo (f . g)

为了使法律更容易掌握，我们以List类型为例:

instance Foldable [a] where
    foldMap f []     = mempty
    foldMap f (x:xs) = f x `mappend` foldMap f xs

-- i.e.
-- foldMap f [a, b, …, w] == f a `mappend` f b `mappend` … `mappend` f w

当我们评估法律的RHS时:

   foldMap (Endo . f)         t
== foldMap (\x -> Endo (f x)) [a, b, …, w]
== (\x -> Endo (f x)) a `mappend`   …   `mappend` (\x -> Endo (f x)) w
== Endo (f a) `mappend` Endo (f b) `mappend`   …   `mappend` Endo (f w)

回想Endo的mappend是组合物，所以上面是

== Endo (f a . f b .   …   . f w)

最后，我们使用appEndo (…) z取出组合函数并将其应用于初始值z:

   appEndo (Endo (f a . f b .   …   . f w)) z
== (f a . f b .   …   . f w)                z
== f a (f b (  …  (f w z)  …  ))

这正是列表的foldr的定义。
foldl是相似的， Dual 是另一个monoid实例，其中Dual a `mappend` Dual b == Dual (b `mappend` a)和getDual取出内部monoid。应该很容易看出这是如何产生foldl的。
fold函数将可折叠的monoid折叠为单个monoid。再次以列表为例，fold可以实现为

fold [a, b, …, w] == a `mappend` b `mappend` … `mappend` w

可以从foldMap检索:

foldMap id [a, b, …, w] == id a `mappend` id b `mappend` … `mappend` id w
                        == a `mappend` b `mappend` … `mappend` w

这显示了如何建议身份fold = foldMap id。