與 foldl

這就是左側摺疊的實現方式。注意與 foldr(右側摺疊)相比,step 函式中引數的順序是如何翻轉的:

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

左側摺疊 foldl 與左側相關聯。那是:

foldl (+) 0 [1, 2, 3]     -- is equivalent to ((0 + 1) + 2) + 3

原因是 foldl 被評估為這樣(看看 foldl 的歸納步驟):

foldl (+) 0 [1, 2, 3]                        --  foldl (+)    0   [ 1,   2,   3 ]
foldl (+) ((+) 0 1) [2, 3]                   --  foldl (+)   (0 + 1)   [ 2,   3 ]
foldl (+) ((+) ((+) 0 1) 2) [3]              --  foldl (+)  ((0 + 1) + 2)   [ 3 ]
foldl (+) ((+) ((+) ((+) 0 1) 2) 3) []       --  foldl (+) (((0 + 1) + 2) + 3) []
((+) ((+) ((+) 0 1) 2) 3)                    --            (((0 + 1) + 2) + 3)

最後一行相當於 ((0 + 1) + 2) + 3。這是因為 (f a b) 一般與(a `f` b)相同,所以 ((+) 0 1) 特別與 (0 + 1) 相同。