浏览 4424 次
锁定老帖子 主题:强大的 fold
精华帖 (0) :: 良好帖 (1) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2009-04-12
最后修改:2009-05-10
基本定义(Prelude.foldr): -- 从右往左卷 foldl f z [] = z foldl f z (x : xs) = foldl f (f z x) xs -- 从左往右卷 foldr f z [] = z foldr f z (x : xs) = f x (foldr f z xs) 另一种定义方式是通过 CPS 。 令 z = 第一个元素,就得到变种 foldl1, foldr1。 注意 foldl 虽然是尾递归,但是消耗内存和 foldr 一样: 延迟求值使 f z x 不会马上被计算出来,依然会产生很大的调用栈。 省内存(strict 版本, Data.List.foldl')的定义如下: foldl' f z [] = z foldl' f z (x:xs) = let z' = f z x in z' `seq` foldl' f z' xs -------------------------------------------------------------------------- 很多常用的函数都可以通过 fold 产生: sum = foldl (+) 0 product = foldl (*) 1 and = foldl1 (&&) or = foldl1 (||) (++) ys = foldr (:) ys length = foldl (\n x -> 1 + n) 0 reverse = foldl (\ys x -> x : ys) [] map f = foldr (\x ys -> f x : ys) [] filter p = foldr (\x ys -> if p x then x : ys else ys) [] 下面,let fold = foldr,看看还能玩什么花样。 --------------------------------------------------------------------------- “融”定理(the fusion property of fold) 如果 h (g x z) = f x (h z) 那么 h . fold g z = fold f (h z) 应用举例: (* 3) . sum = (* 3) . fold (+) 0 所以这里 h = (* 3), g = (+) 令 f x y = x * 3 + y,则有 h (g x z) = f x (g z) 再根据上面的定理 (* 3) . sum = fold f (h 0) = fold (\x y -> x * 3 + y) 0 也就是说,列表中所有元素的和乘以 3 ,等于每个元素乘 3 再求和。 这个结论人脑想很浅显,但机器想就不是这回事了。 fold 的这个性质给机器推理提供了新的方法。 一些算法写出来简单易读,但是运行效率很低。利用这个性质进行变换,可以在不影响可读性的前提下优化算法。 ghc 里面就有不少这样的优化。 ---------------------------------------------------------------------------- “切香蕉”性质(banana split property of fold) 梅姐 good job! 假设我们要计算和、平方和、立方和 sum'squareSum'cubicSum l = (sum l, squareSum l, cubicSum l) 这样我们要遍历这个 list 3 遍。(这个问题在 C++ 模板编程中也经常遇到呢) 但是用 fold 就不一样了: sum'squareSum'cubicSum = foldr (\x (s1, s2, s3) -> (s1 + x, s2 + x ^ 2, s3 + x ^ 3)) (0, 0, 0) ---------------------------------------------------------------------------- 源生递归 = fold 在递归神教的教义中可以找到源生递归(primitve recursion)的通用模式: h y [ ] = f y h y (x : xs) = g y x xs (h y xs) 假定递归函数如上式定义,取出 f 和 g,然后用 fold 定义 k 如下: k y = fold i j where i x (z, xs) = (g y x xs z, x : xs) j = (f y, []) 最后,我们得到的 k 是这么一个东西,它满足: k y xs == (h y xs, xs) 于是…… 万物至 fold …… (也不尽然,像 Ackman 函数那样的高阶递归就不能轻易的写成 fold) 由于 fold 已经自带边界条件,所以用 fold 表达的函数不用写两行: --组合 list 内的所有函数 compose = foldr (.) id foldl 也可以用 foldr 表示: foldl f v xs = fold (\x g -> (\a -> g (f a x))) id xs v 可惜如果不引入递归,foldr 没法用 foldl 表示——这也体现了命令式的循环的弱点。 ----------------------------------------------------------------------------- 推荐 paper: http://www.cs.nott.ac.uk/~gmh/fold.pdf 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |