Prelude.foldl
foldl
为 left-associative folding。
foldl :: (b -> a -> b) -> b -> [a] -> b |
foldl (+) 0 [1..3]
等价于 (((0 + 1) + 2) + 3)
。
- 尾递归,因此有 strict 版本
foldl'
- 求值时必须先到达栈底,遍历完列表,因此无法处理无穷列表
Data.List.foldl’
foldl'
为 foldl
的 TRO 版本。
Prelude.foldr
foldr
为 right-associative folding。
foldr :: (a -> b -> b) -> b -> [a] -> b |
foldr (+) 0 [1..3]
等价于 (0 + (1 + (2 + 3)))
- 没有尾递归,有爆栈的危险。
- 有向右展开的特点,而 Haskell 中许多数据结构都有向右递归的特点(如 Cons),因此可以很好地处理无穷递归的数据,从而更加通用。
Prelude.foldl1 && Prelude.foldr1
Helper functions。将 operator 限制为同一种类型,同时约去 accumulator。
foldl1 :: (a -> a -> a) -> [a] -> a |
即,foldr1
将列表的第一个值作为 accumulator,将剩余部分作为 list,传给 foldr
。foldl
同理。
实践
用 folds 实现 reverse
reversel, reverser :: [a] -> [a] |
用 foldr 实现 foldl
先归纳出 foldr
的泛性质。如果一个函数 g
s.t.
g [] = v |
则 g list === foldr f v list
.
再看 foldl
的定义:
foldl f v [] = v |
应有 g (x:xs) === k x (g xs)
,我们计算 k
:
g (x:xs) === k x (g xs) |
所以
foldl f v xs = |
OOPS!
A comment box should be right here...But it was gone due to network issues :-(If you want to leave comments, make sure you have access to disqus.com.