Haskell Language Lists foldr
Example
This is how the right fold is implemented:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs) -- = x `f` foldr f z xs
The right fold, foldr, associates to the right. That is:
foldr (+) 0 [1, 2, 3] -- is equivalent to 1 + (2 + (3 + 0))
The reason is that foldr is evaluated like this (look at the inductive step of foldr):
foldr (+) 0 [1, 2, 3] -- foldr (+) 0 [1,2,3]
(+) 1 (foldr (+) 0 [2, 3]) -- 1 + foldr (+) 0 [2,3]
(+) 1 ((+) 2 (foldr (+) 0 [3])) -- 1 + (2 + foldr (+) 0 [3])
(+) 1 ((+) 2 ((+) 3 (foldr (+) 0 []))) -- 1 + (2 + (3 + foldr (+) 0 []))
(+) 1 ((+) 2 ((+) 3 0)) -- 1 + (2 + (3 + 0 ))
The last line is equivalent to 1 + (2 + (3 + 0)), because ((+) 3 0) is the same as (3 + 0).
