Folds

Three folds

All folds replace the constructors of a structure with a function. The difference is the direction and the strictness:

foldr :: (a -> b -> b) -> b -> [a] -> b -- right, lazy foldl :: (b -> a -> b) -> b -> [a] -> b -- left, lazy accumulator foldl' :: (b -> a -> b) -> b -> [a] -> b -- left, strict

Note the flipped argument order: foldr takes the element first, the left folds take the accumulator first. That single detail decides which lambdas typecheck.

Derive functions from folds

Most list functions are a fold with a particular combining function. Writing them this way proves you understand the structure:

mySum = foldr (+) 0 myProduct = foldr (*) 1 myMap f = foldr (\x acc -> f x : acc) [] myFilter p = foldr (\x acc -> if p x then x : acc else acc) [] myLength = foldr (\_ acc -> acc + 1) 0

myMap and myFilter use foldr because they build a list, and building with cons from the right is what preserves order.

foldMap

When the elements can be combined pairwise, the combining function is already defined by a Monoid instance. foldMap needs only the projection:

foldMap show [1,2,3] -- "123" foldMap Sum [1,2,3] -- Sum 6 foldMap (\x -> [x, x]) [1,2] -- [1,1,2,2]

The third line works because lists are monoids under concatenation, which makes foldMap a generalisation of concatMap. Lesson 43 opens the class.

Choosing a fold

The decision table is short. Use the strict left fold for numbers and the right fold for lists and short-circuiting:

-- sum of a big list: strict, constant memory foldl' (+) 0 xs -- rebuild a list: lazy, can stop early foldr (:) [] xs -- combine with a monoid: no lambda at all foldMap show xs

Plain foldl has no column in that table. It exists for historical reasons and for the rare case where the accumulator must stay lazy on purpose.

Next: Monoids

Article author: Arthur Isaev