没有折叠的折叠有什么特性？

Question

Foldl和folr是FP和Haskell的两个非常重要的函数,但是我从来没有听过太多关于unsided fold的内容:

fold f [a,b,c,d] = (f (f a b) (f c d))

也就是说,操作二进制关联函数的折叠(因此应用顺序无关紧要).如果我没记错的话,这在数据库中很常见,因为它可以并行化.所以,关于它,我问:

1. 像折叠一样,它是普遍的吗？
2. 像foldr一样,你能用它定义每个重要的功能吗？
3. 是否有融合规则,类似于foldr/build和unfoldr/destroy？
4. 为什么几乎没有提到？
5. 还有什么值得一提的考虑？

Answer 1

这通常被认为是树木减少,并且在并行计算中很重要,因为它体现了分而治之的减少.

首先,如果结合功能非关联则显然有存在很大的不同foldl,foldr以及"unsided折",让我们假设,我们结合了关联操作.立即,所有折叠都可以用a表示Monoid.

foldlm :: Monoid m => [m] -> m
foldlm = foldl mappend mempty

foldrm :: Monoid m => [m] -> m
foldrm = foldr mappend mempty

usfoldm :: Monoid m => [m] -> m
usfoldm = foldTree mappend mempty . buildTree

哪个更好地表示foldMap :: Monoid m => (a -> m) -> [a] -> m默认使用哪个定义foldr.

foldMap f = foldr (mappend . f) mempty

如果给出最终提取步骤,这足以产生树状无边折叠,给Monoid定在树状序列类型上的定义,该类型控制元素如何Monoid组合.

data Tree a
singleton :: a -> Tree a
instance Monoid (Tree a) where ...
foldTree :: Monoid a => Tree a -> a

foldTree . foldMap singleton :: Monoid a => [a] -> a

最后,我们已经看到我们可以从中foldMap获益foldr,但我们也可以从中foldr获益foldMap

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

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

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

通常,foldMap被认为更原始,因为它让底层Monoid选择其首选的折叠方法.这意味着我们可以在每个数据类型级别上自由编写更高效或更平行的折叠,尽管正确地执行此操作仍然具有挑战性.

值得注意的是,foldMap抽象通常被认为是一种实例方法,Foldable它是一种非常流行但更新的Haskell类型类.尽管它具有实用性,但它也被认为有点愚蠢,因为Foldable除了这一点之外几乎没有什么有意义的法律

toList :: Foldable f => f a -> [a]

存在,这也让我们看到了Monoid的人,自然foldMap是[a]为通用Monoid,我们可以恢复foldr.

为了进一步研究融合规则,阅读BuildableGershom Bazerman 通过附录建立一个点的双类型类是很有价值的.

最后,至于受欢迎程度,我认为它绝对是实例化Foldable这些日子的首选方法,因为它可以Monoid在必要时允许更有效的折叠,但它肯定比两者都更新foldl,foldr并且可能会发挥其相对默默无闻的作用.

Answer 2

您正在寻找的功能是Data.Foldable.foldMap.

foldMap :: Data.Monoid.Monoid m => (a -> m) -> t a -> m

该函数同构于foldr. 作为证明，请注意 或 之一foldMap是foldr的最小完整定义Foldable，这意味着每个都可以用另一个来编写。这肯定地回答了你的前两个问题。

我不知道foldMap具体的融合规则，但我确信可能存在。至少，foldr 融合规则应该在某种程度上适用。

我不知道为什么很少有人提到它。

值得一提的一个考虑因素是，就列表而言，您不能总是充分利用这种折叠。foldl由于列表是由 cons 单元格构建的，因此进行树折叠意味着遍历列表的一半，然后向下递归每一半并再次遍历一半，等等。与or相比，这是很多额外的遍历foldr。对于非列表结构，树折叠可以更有效，甚至对于列表也可以利用这一点。最近有一篇关于此类任务的精彩博客。