我只是好奇,如果有任何(只有一阶多态)优化与折叠。优化与折叠
对于地图,有森林砍伐:map g (map f ls) => map (g . f) ls
和rev (map f ls) => rev_map f ls
(在Ocaml更快)。
但折叠是如此强大,它似乎无视任何优化。
我只是好奇,如果有任何(只有一阶多态)优化与折叠。优化与折叠
对于地图,有森林砍伐:map g (map f ls) => map (g . f) ls
和rev (map f ls) => rev_map f ls
(在Ocaml更快)。
但折叠是如此强大,它似乎无视任何优化。
显而易见的:
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。
这是一个有趣的纸,是的,我读过它:) – Yttrill 2011-02-01 02:02:14
您可以在褶皱上使用砍伐森林。实际上,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之类的转换。
如果您有兴趣进一步了解理论,我建议您阅读一些关于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
结果。
你可能也想在理论CS页面上发表这个问题 – blueberryfields 2011-01-31 13:48:40
@blueberryfields:[理论计算机科学栈交换](http://cstheory.stackexchange.com/)是针对研究级别的TCS,这个问题是“T。 @Yttril:折叠是一种通用操作(数据结构上的每个连续动作都可以表示为折叠),这表明很少有这样的等式成立。 – Gilles 2011-01-31 20:54:25
@Giles:是的,这就是为什么我很好奇实际上有多少优化。 – Yttrill 2011-02-01 02:13:14