map, filter, and foldr

map and filter

Two of the three standard traversals transform a list without changing its length or keeping only some elements:

map (*2) [1,2,3] -- [2,4,6] filter even [1..10] -- [2,4,6,8,10] map show [1,2] ++ map show [3] -- ["1","2","3"]

Both take a function and a list, which is exactly what partial application from lesson 8 makes cheap. Chained, they replace most loops you would write in another language.

foldr

A fold replaces the constructors of a list with a function and a starting value. foldr works from the right, which is the same direction as the cons chain:

foldr (+) 0 [1,2,3] -- 6 foldr (:) [] [1,2,3] -- [1,2,3] foldr (\x acc -> x : acc) [] [1,2] -- [1,2]

The substitution view is exact: foldr f z [a,b,c] equals f a (f b (f c z)). Once you see that, every fold-based function is readable.

foldl and foldl1

foldl works from the left and carries an accumulator, which matches the loop you would write by hand:

foldl (+) 0 [1,2,3] -- 6 foldl (flip (++)) [] ["a","b"] -- ["b","a"] foldl1 (+) [1,2,3] -- 6, first element is the start

foldl1 and foldr1 drop the starting value and take the first or last element instead. They crash on an empty list, so they are partial functions.

Which one

foldr can stop early on an infinite list and works well when the combining function is lazy in its second argument. foldl cannot, and it builds a huge thunk, which is why the strict version foldl' exists:

-- works on an infinite list take 3 (foldr (\x acc -> x : acc) [] [1..]) -- strict left fold, the safe default for sums foldl' (+) 0 [1..1000000]

Use foldr to build a list or to short-circuit, and foldl' to accumulate a number. Plain foldl is almost always a mistake, and lesson 41 shows exactly why.

Next: Lambdas and composition

Article author: Arthur Isaev