foldl和foldr的不同點

foldl

foldl這個函數的類型是：

(a -> b -> a) -> a -> [b] -> b

它接收一個函數、一個起始值、一個列表。它的作用相當于：

foldl f z [x_1, x_2, ..., x_n] ==
(... ((z `f` x_1) `f` x_2) `f` ...) `f` x_n

也就是它把起始值作爲f的*左參數*，從左邊迭代列表。

可以這樣實現這個函數：

mfoldl' :: (a -> b -> a) -> a -> [b] -> a
mfoldl' f accu [] = accu
mfoldl' f accu (x : xs) =
  mfoldl' f (accu `f` x) xs

λ> mfoldl' (-) 0 [1..3]
-6

foldr

foldr這個函數的類型是：

(a -> b -> b) -> b -> [a] -> b

它的作用相當于：

foldr f z [x_1, x_2, ..., x_n] == 
(x_1 `f` (x_2 `f` (... (x_n `f` z)...)))

它把起始值作爲f的*右參數*，從右邊開始迭代列表。

這樣實現這個函數：

mfoldr' :: (a -> b -> b) -> b -> [a] -> b
mfoldr' f accu [] = accu
mfoldr' f accu (x : xs) =
  x `f` (mfoldr' f accu xs)

λ> mfoldr' (-) 0 [1..3]
2

其實單單從函數的類型上就能夠得到很多信息。這也是強類型語言的一個優點吧。