[Haskell] foldr与foldl

1. foldr定义

foldr f z (x : xs) = f x (foldr f z xs) 
foldr f _ [] = _  

例子：

foldr + 0 [1 2]
= + 1 (foldr + 0 [2])
= + 1 (+ 2 (foldr + 0 []))
= + 1 (+ 2 0)
= 3

2. foldl定义

foldl f z (x : xs) = foldl f (f z x) xs 
foldl f _ [] = _ 

例子：

foldl + 0 [1 2]
= foldl + (+ 0 1) [2]
= foldl + (+ (+ 0 1) 2) []
= + (+ 0 1) 2
= 3

3. 使用foldr定义foldl

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

注：
（1）可以使用一个temp函数简化定义，

foldl f v xs = foldr temp id xs v
    where temp x g = \a->g (f a x)

（2）Currying以后还可以写为，

foldl f v xs = foldr temp id xs v
    where temp x g a = g (f a x)

例子：

foldl + 0 [1 2]
= foldr temp id [1 2] 0

 foldr temp id [1 2]
= temp 1 (foldr temp id [2])
= temp 1 (temp 2 (foldr temp id []))
= temp 1 (temp 2 id)
= temp 1 (\a->id (+ a 2))
= temp 1 (\a->+ a 2)
=\a->(\a->+ a 2) (+ a 1)
=\a->+ (a + 1) 2

foldr temp id [1 2] 0
=(\a->+ (a + 1) 2) 0
=+ (0 + 1) 2
=3