Folds

Very often, we want to combine all the elements of a list together in some manner. Some examples:

• the sum of a list of integers

add_all :: [Integer] -> Integer
add_all []     = 0
add_all (x:xs) = x + add_all xs

• the product of a list of numeric values

mul_all :: [Integer] -> Integer
mul_all []     = 1
mul_all (x:xs) = x * (mul_all xs)

• the concatenation of a list of string values

join_all :: [[Char]] -> [Char]
join_all []     = []
join_all (x:xs) = x ++ (join_all xs)

• the conjunction of a list of boolean values

all_true :: [Bool] -> Bool
all_true []     = True
all_true (x:xs) =  x && (all_true xs)

Each of these functions exhibits a common computational pattern, known in Haskell as foldr: fold from the right.

add_all x = foldr (+) 0 x
mul_all x = foldr (*) 1 x
join_all x = foldr (++) [] x
all_true x = foldr (&&) True x

In general, folding is the repeated application of a binary function f to a list of elements starting with an initial accumulator value acc.

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

In general, the type of list elements a can differ from the type of the accumulated result b. (In which of our examples above are the types actually different?)

Folding from the right means that the list elements are combined into the result in right-to-left order.

foldr (+) 0 [1,2,3] = (+) 1 (foldr (+) 0 [2,3])
                    = (+) 1 ((+) 2 (foldr (+) 0 [3]))
                    = (+) 1 ((+) 2 ((+) 3 (foldr (+) 0 [])))
                    = (+) 1 ((+) 2 ((+) 3 0))
                    = (+) 1 ((+) 2 3)
                    = (+) 1 5
                    = 6

Folding from left

Folding from the right may not always give what we expect:

Prelude> foldr (-) 0 [1, 2, 3]
2

This is because of the right-to-left processing:

foldr (-) 0 [1, 2, 3] = (1 - (2 - (3 - 0)))

Instead we can use foldl for right-to-left processing.

Prelude> foldl (-) 0 [1, 2, 3]
-6

This reflects the left-to-right processing that we might expect.

foldr (-) 0 [1, 2, 3] = (((0 - 1) - 2) - 3)

Simplified folding

In many cases, when the type of the result being computed is the same as the list element type, we can simplify the folding by taking the initial element being accumulated from the list itself.

The foldr1 function uses the last (rightmost) element of the list as an initial accumulator value. Our previous examples all become simplified.

add_all x = foldr1 (+) x
mul_all x = foldr1 (*) x
join_all x = foldr1 (++) x
all_true x = foldr1 (&&) x

But this only works when the type of both operands of the fold function (as well as the result type) are the same.

foldr1           :: (a -> a -> a) -> [a] -> a
foldr1 f [x]     =  x
foldr1 f (x:xs)  =  f x (foldr1 f xs)
foldr1 _ []      =  error "Prelude.foldr1: empty list"

foldr1 is particularly useful when the fold function has a natural right identity element i such that

f x i = x

Similarly foldl1 uses the leftmost element as the initial accumulator value, working well when the folded function has a natural left identity element.

List Comprehensions

• https://en.wikibooks.org/wiki/Haskell/Lists_III