当Tree实现可折叠折叠图时,Foldr/Foldl是免费的吗？

Question

我是Haskell的初学者,并且从"了解你一个Haskell"中学到了一些我对Foldable的Tree实现不了解的东西.

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  

引用来自:LYOH:"因此,如果我们只为某种类型实现foldMap,我们可以免费获得该类型的foldr和foldl!"

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

Answer 1

我们从以下类型开始foldMap:

foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m

foldMap通过a -> m在数据结构上映射函数然后运行它将元素粉碎成单个累积值来工作mappend.

接下来,我们注意到,给定某种类型b,b -> b函数形成一个monoid,具有(.)二进制操作(即mappend)和id标识元素(即,mempty如果尚未满足它,id则定义为id x = x).如果我们专注foldMap于那个幺半群,我们会得到以下类型:

foldEndo :: Foldable t => (a -> (b -> b)) -> t a -> (b -> b)

(我调用了函数,foldEndo因为endofunction是从一种类型到同一类型的函数.)

现在,如果我们看一下列表的签名 foldr

foldr :: (a -> b -> b) -> b -> [a] -> b

我们可以看到foldEndo匹配它,除了对any的泛化Foldable和对参数的一些重新排序.

在我们开始实现之前,存在技术复杂性,b -> b不能直接成为实例Monoid.为了解决这个问题,我们改为使用Endonewtype包装Data.Monoid:

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

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

用来写的Endo,foldEndo只是专门的foldMap:

foldEndo :: Foldable t => (a -> Endo b) -> t a -> Endo b

因此,我们将直接跳转到foldr并根据其进行定义foldMap.

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo . f) t) z

您可以找到Data.Foldable哪个默认定义.最棘手的可能是Endo . f; 如果你遇到麻烦,可以考虑f不是二元运算符,而是作为一个带有类型的参数的函数a -> (b -> b); 然后我们将结果的endofunction包装起来Endo.

至于foldl,推导基本上是相同的,除了我们使用不同的内部函数monoid,flip (.)作为二元运算(即我们在相反的方向上组合函数).

Answer 2

文件夹始终可以定义为：

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

其中appEndo和Endo只是新类型的包装器/包装器。实际上，这段代码是直接从Foldable类型类中提取的。因此，通过定义foldMap，您可以自动获取foldr。