# Haskell 笔记：folds

## Prelude.foldl

`foldl` 为 left-associative folding。

`foldl :: (b -> a -> b) -> b -> [a] -> bfoldl f acc [] = accfoldl 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] -> bfoldr f acc [] = accfoldr 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] -> afoldl1 f (x:xs) = foldl f x xsfoldl1 _ [] = errorfoldr1 :: (a -> a -> a) -> [a] -> afoldr1 f (x:xs) = foldr f x xsfoldr1 _ [] = error`

## 实践

### 用 folds 实现 `reverse`

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

### 用 foldr 实现 foldl

`g [] = vg (x:xs) = f x (g xs)`

`g list === foldr f v list`.

`foldl f v [] = vfoldl 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)g (x:xs) v     === k x (g xs) vg xs (f v x)   === k x (g xs) v(g xs) (f v x) === k x (g xs) vg' (f v x)     === k x g' vk              === \x g' v -> g' (f v x)`

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

## 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.