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:
import Data.List (foldl')
foldl (+) 0 [1,2,3] -- 6
foldl (flip (++)) [] ["a","b"] -- "ba"
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.
The code on this page was run with GHC 9.10.3 on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev