如何理解可折叠实例的规则？

Question

如何理解可折叠实例的规则？

6

在描述Data.Foldable的页面上，它说： 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？

- user28522

1

相关：当Tree实现Foldable foldmap时，是否可以免费获得Foldr/Foldl？（我在那里的答案与kennytm在这里的答案涵盖了相同的内容，但以稍微不同的方式讲述了故事。） - duplode

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kennytm · Accepted Answer

Endo是“通过组合运算的自同态幺半群”。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

当我们评估法律的右侧时：

   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 是另一个单子实例，其中 Dual a `mappend` Dual b == Dual (b `mappend` a)，而 getDual 取出内部单子。很容易看出这如何产生 foldl。

fold函数将可折叠的单子折叠成一个单一的单子。再次以列表为例，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。