当 Tree 实现可折叠 foldMap 时，Foldr/Foldl 免费? [英] Foldr/Foldl for free when Tree is implementing Foldable foldMap?

问题描述

我是 Haskell 的初学者，正在学习Learn You a Haskell".

I am a beginner at Haskell and learning from "Learn You a Haskell".

关于Foldable 的Tree 实现，我有些不明白.

There's something I don't understand about the Tree implementation of Foldable.

instance F.Foldable Tree where  
    foldMap f Empty = mempty  
    foldMap f (Node x l r) = F.foldMap f l `mappend`  
                             f x           `mappend`  
                             F.foldMap f r  

引自 LYAH:因此，如果我们只是为某种类型实现 foldMap， 我们会得到 foldr 和 foldl在那种类型上免费！".

Quote from LYAH: "So if we just implement foldMap for some type, we get foldr and foldl on that type for free!".

有人能解释一下吗?我不明白我现在如何以及为什么免费获得 foldr 和 foldl...

Can someone explain this? I don't understand how and why do I get foldr and foldl for free now...

推荐答案

foldr 总是可以定义为:

foldr can always be defined as:

foldr f z t = appEndo (foldMap (Endo . f) t) z

其中 appEndo 和 Endo 只是新型解包器/包装器.事实上，这段代码是直接从 Foldable 类型类中提取出来的.所以，通过定义foldMap，你会自动得到foldr.

where appEndo and Endo are just newtype unwrappers/wrappers. In fact, this code got pulled straight from the Foldable typeclass. So, by defining foldMap, you automatically get foldr.

这篇关于当 Tree 实现可折叠 foldMap 时，Foldr/Foldl 免费?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！