Foldl 和 folr 是 FP 和 Haskell 的两个非常重要的函数,但我从未听说过太多关于侧折叠的信息:
fold f [a,b,c,d] = (f (f a b) (f c d))
也就是说,在二进制关联函数上运行的折叠(因此应用程序的顺序无关紧要)。如果我没记错的话,这在数据库中很常见,因为它可以并行化。所以,关于它,我问:
- 它像折叠器一样,是通用的吗?
- 像折叠器一样,你能用它定义每个重要的函数吗?
- 它是否有融合规则,类似于折叠/构建和解展开/销毁的规则?
- 为什么很少被提及?
- 有什么值得一提的考虑吗?
这通常被认为是树约简,在并行计算中很重要,因为它体现了分而治之的归约。
首先,如果组合函数是非结合函数,那么显然foldl
、foldr
和"无侧折叠"之间存在很大差异,所以让我们假设我们与结合运算组合。立即,所有折叠都可以用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
默认情况下使用foldr
定义的foldMap :: Monoid m => (a -> m) -> [a] -> m
更好地表示哪个。
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
最后,我们已经看到我们可以从foldr
中得到foldMap
,但我们也可以从foldMap
中得到foldr
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]
存在,这也让我们看到了foldMap
的Monoid
性,因为[a]
是我们可以通过foldr
恢复的普遍Monoid
。
为了进一步研究融合规则,阅读一个提议的双类型类Buildable
是有价值的,如Gershom Bazerman的通过Adjunctions建立到一个点。
最后,至于流行度,我认为它绝对是当今实例化Foldable
的首选方法,因为它允许在必要时更有效的Monoid
折叠,但它肯定比foldl
和foldr
都更新,这可能会发挥其相对晦涩的作用。
您要查找的函数是Data.Foldable.foldMap
。
foldMap :: Data.Monoid.Monoid m => (a -> m) -> t a -> m
此函数与foldr
同构。 作为证明,请注意foldMap
或foldr
中的一个是Foldable
的最小完整定义,这意味着每个都可以用另一个来写。 这肯定地回答了你的前两个问题。
我不知道foldMap
的具体融合规则,但我确信可能存在。 至少,折叠融合规则应该在一定程度上适用。
我不知道为什么它很少被提及。
值得一提的一个考虑因素是,就列表而言,您不能总是充分利用这种折叠。 由于列表是由缺点单元格构建的,因此进行树折叠意味着遍历列表的一半,然后递归每一半并再次遍历一半,依此类推。 与foldl
或foldr
相比,这是很多额外的遍历。 对于非列表结构,树折叠可以更有效,即使对于列表,也可以利用这一点。 最近有一个关于这样一个任务的很好的博客。