优化与折叠

Question

我只是好奇，如果有任何（只有一阶多态）优化与折叠。

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

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

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

编辑：我的第一个规则的第一个版本是错误的，编辑的感谢文森特 - 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 

（其实这只有在确定，但常见的情况。详情请参阅"Correctness of short-cut fusion"）。

如果你写你的列表产生功能使用foldr使用build和你的消费者（包括map），那么上面的等式可以去除最中间的列表。 Haskell的列表解析被翻译成build和foldr的组合。

这种方法的缺点是它不能处理左褶皱。 Stream Fusion可以解决这个问题。它将列表生成器和变换器表示为流（coinductive数据类型，有点像迭代器）。上面的文章非常可读，所以我建议看看。

gasche提到的“香蕉”论文更详细地介绍了各种褶皱及其等价性。

最后，还有Bird和Moor的"Algebra of Programming"，其中提到了诸如combining two folds into one之类的转换。

Answer 3

如果您有兴趣进一步了解理论，我建议您阅读一些关于catamorphisms,anamorphisms和hylomorphisms的内容。围绕它的分类理论似乎有点可怕，但这个概念并不困难。

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

现在，如果您建立具有变形的递归数据结构，然后将其与变形消耗相结合，就会得到所谓的“ hylomorphism。在这种情况下，你实际上不需要中间结构。你可以跳过创建并销毁它。这通常被称为deforestation。

---

关于map：此功能有趣的是，这是一个既catamorphism 和的anamorphism：

• map消费清单，并产生一些;但也
• map产生一个列表，消耗的东西。

所以可以查看两个映射map f . map g作为anamorphism（map g）与catamorphism（map f）的组合物的组成，形成了hylomorphism。所以你知道可以通过不创建中间列表来优化（森林砍伐）。

要具体：你可以写两个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)为mapCata f (mapAna g zs)，这之后一些简化和map (f . g)应用foldr c n (build g) == g c n结果。