performance - 折叠优化

Question

我只是好奇是否有任何（仅限一阶多态）折叠优化。

对于地图，有森林砍伐：map g (map f ls) => map (g . f) ls和rev (map f ls) => rev_map f ls（在 Ocaml 中更快）。

但是 fold 是如此强大，它似乎无视任何优化。

Answer 1

显而易见的：

fold_left f acc (List.map g li) => fold_left (fun acc x -> f acc (g x)) acc li
fold_right f li acc => fold_left f acc li (* if (f,acc) is a monoid *)

您可能对有关主题的经典论文“香蕉、镜头、信封和铁丝网的函数式编程”感兴趣。但是请注意，它是技术性的并且具有难以理解的符号。

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125

编辑：我的第一条规则的第一个版本是错误的，感谢 vincent-hugot 编辑。

Answer 2

您可以在褶皱上使用森林砍伐。事实上，map/map聚变是其中的一个特例。

诀窍是用特殊build函数替换列表构造：

build :: (forall b. (a -> b -> b) -> b -> b) -> [a]
build g = g (:) []

现在，使用标准定义foldr

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr c n []     = n
foldr c n (x:xs) = c x (foldr c n xs)

我们有以下等价性：

foldr c n (build g) == g c n

（实际上，这仅在某些但常见的情况下才成立。有关详细信息，请参阅“捷径融合的正确性”）。

如果您编写列表生成函数（包括map） usingbuild和您的消费者 using foldr，则上述等式可以删除大多数中间列表。Haskell 的列表推导被翻译成build和的组合foldr。

这种方法的缺点是它不能处理左折叠。 不过， Stream Fusion可以很好地处理这个问题。它将列表生产者和转换器表示为流（汇合数据类型，有点像迭代器）。上面的论文可读性很强，所以我建议看一下。

加什提到的“香蕉”论文更详细地介绍了褶皱的种类及其等价物。

最后，还有 Bird 和 Moor 的“Algebra of Programming”，其中提到了将两个折叠合二为一等变换。

Answer 3

如果您有兴趣深入了解理论，我建议您阅读有关catamorphisms、anamorphisms和hylomorphisms的内容。虽然围绕它的范畴理论可能看起来有点吓人，但这个概念并不难。

Catamorphisms 是使用递归数据结构并产生某种值的函数。变形是给定一些值（一种种子）产生递归数据结构的函数。特别是，在其他答案foldr中build提到的是在列表上构建变态和变态的函数。但是这个概念基本上可以应用于任何递归数据结构，例如不同种类的树等。

现在，如果您使用变形构建递归数据结构，然后使用变形来使用它，您就会得到所谓的hylomorphism。在这种情况下，您实际上不需要中间结构。您可以跳过创建和销毁它。这通常被称为森林砍伐。

---

关注map点：这个函数很有趣，它既是变形又是变形：

• map消费一个列表并产生一些东西；但是也
• map产生一个列表，消耗一些东西。

因此，您可以将两个映射map f . map g的组合视为变形 ( map g) 与变质 ( map f) 的组合，形成一个hylomorphism。所以你知道可以通过不创建中间列表来优化（deforest）。

具体来说：您可以用map两种方式编写，一种使用foldr，另一种使用build：

mapAna :: (a -> b) -> [a] -> [b]
mapAna f xs = build (mapAna' f xs)

mapAna' :: (a -> b) -> [a] -> (b -> c -> c) -> c -> c
mapAna' f []       cons nil = nil
mapAna' f (x : xs) cons nil = (f x) `cons` (mapAna' f xs cons nil)


mapCata :: (a -> b) -> [a] -> [b]
mapCata f xs = foldr (\x ys -> f x : ys) [] xs

和组合map f (map g zs)as mapCata f (mapAna g zs)，经过一些简化和应用后foldr c n (build g) == g c n得到map (f . g).