Haskell Language Lists foldl
Example
This is how the left fold is implemented. Notice how the order of the arguments in the step function is flipped compared to foldr (the right fold):
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
The left fold, foldl, associates to the left. That is:
foldl (+) 0 [1, 2, 3] -- is equivalent to ((0 + 1) + 2) + 3
The reason is that foldl is evaluated like this (look at foldl's inductive step):
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)
The last line is equivalent to ((0 + 1) + 2) + 3. This is because (f a b) is the same as (a `f` b) in general, and so ((+) 0 1) is the same as (0 + 1) in particular.
