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).