function - 非边褶皱的特性是什么？

Question

Foldl 和 folr 是 FP 和 Haskell 的两个非常重要的函数，但我从未听说过太多关于非边折叠的信息:

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

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

它像foldr一样通用吗？

像 foldr 一样，你能用它定义每一个重要的功能吗？

是否有它的融合规则，类似于 foldr/build 和展开器/destroy 的融合规则？

为什么很少提及？

有什么值得一提的考虑吗？

Answer 1

这通常被认为是树归约，并且在并行计算中很重要，因为它体现了分而治之的归约。

首先，如果组合函数是非关联的，那么 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

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

foldMap f = foldr (mappend . f) mempty

如果给定一个最终提取步骤，这足以在给定 Monoid 的情况下产生树状非边折叠。在树状序列类型上定义，该类型控制元素 - Monoid s 组合在一起。

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 恢复.

为了进一步研究融合规则，阅读有关提议的双类型类 Buildable 将是有值(value)的。如 Gershom Bazerman 的 Building up to a Point via Adjunctions .

最后，至于受欢迎程度，我认为它绝对是实例化 Foldable 的首选方法。这些天来，因为它允许更高效Monoid必要时可折叠，但绝对比 foldl 都更新和 foldr这可能会影响其相对默默无闻。