Haskell 笔记：folds

Prelude.foldl

foldl 为 left-associative folding。

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f acc [] = acc
foldl f acc (x:xs) = foldl f (f acc x) xs

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 f acc [] = acc
foldr f acc (x:xs) = f x (foldr f acc xs)

foldr (+) 0 [1..3] 等价于 (0 + (1 + (2 + 3)))

• 没有尾递归，有爆栈的危险。
• 有向右展开的特点，而 Haskell 中许多数据结构都有向右递归的特点（如 Cons），因此可以很好地处理无穷递归的数据，从而更加通用。

Prelude.foldl1 && Prelude.foldr1

Helper functions。将 operator 限制为同一种类型，同时约去 accumulator。

foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs) = foldl f x xs
foldl1 _ [] = error

foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 f (x:xs) = foldr f x xs
foldr1 _ [] = error

即，foldr1 将列表的第一个值作为 accumulator，将剩余部分作为 list，传给 foldr。foldl 同理。

实践

用 folds 实现 reverse

reversel, reverser :: [a] -> [a]
reversel list = foldl (\acc x -> x : acc) [] list

reverser list = foldr (\x acc -> acc ++ [x]) [] list

用 foldr 实现 foldl

先归纳出 foldr 的泛性质。如果一个函数 g s.t.

g [] = v
g (x:xs) = f x (g xs)

则 g list === foldr f v list.

再看 foldl 的定义：

foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs

===>

foldl f v list = g list v
    where 
        g [] v = v
        g (x:xs) v = g xs (f v x)
        -- 从左到右依次更新 v

===>

foldl f v list = g list v
    where 
        g [] = id
        g (x:xs) = \v -> g xs (f v x)

应有 g (x:xs) === k x (g xs)，我们计算 k：

g (x:xs)       === k x (g xs)
g (x:xs) v     === k x (g xs) v
g xs (f v x)   === k x (g xs) v
(g xs) (f v x) === k x (g xs) v 
g' (f v x)     === k x g' v
k              === \x g' v -> g' (f v x)

所以

foldl f v xs = 
    (foldr
        (\x g' v -> g' (f v x))
        id
        xs
    ) v