map, filter and the fold

Functions are values you can pass around, so three small helpers replace most hand-written walks: change every value, keep some, or boil a list down to one answer.

Part 6 of 12

Intermediate18 min readBack to Courses

Functions are values you can pass

map, filter and foldr are ordinary functions that take another function as an argument. You do not need any special syntax to pass one: a name is enough, as in map double nums. The only requirement is that the function has the type the job needs.

So map needs a function from one value to another, and filter needs a function from a value to a Bool. The type line of the helper you pass tells the compiler which of the two you meant.

Change every value, or keep some

map applies a function to every value and answers a list of the same length. filter keeps the values whose test answers True, so the answer is the same length or shorter. Neither one touches the list it was given: a new list is built and the old one is left exactly as it was.

Because a String is a list of characters, these helpers work on text too. Nothing extra has to be written for that case, and nothing in the language treats text as a special kind of list.

The fold boils a list down

foldr takes three things: a function that combines one value with the answer so far, a starting value for the empty list, and the list. foldr (+) 0 is the sum, and the same shape writes a product, a longest word or a sentence built out of lines.

Prelude already ships sum, product, maximum and length, so use those when they fit and write your own fold when the combination is something the standard ones do not do.

foldl, and which end you start from

foldl is the other fold: it combines from the left, with the accumulator first. foldl (+) 0 and foldr (+) 0 agree, because addition does not care about the grouping. Subtraction does. foldr (-) 0 [1, 2, 3] is 1 - (2 - (3 - 0)), which is 2, while foldl (-) 0 [1, 2, 3] is ((0 - 1) - 2) - 3, which is -6. Same values, same operator, different answer.

The rule is to ask what the starting value means. In foldr, it is the answer for the empty list, and the first value is combined with the answer for the rest. In foldl, it is the answer so far, and each value is folded into it from the left. For a sum the two agree; for building a list or a sentence, the difference is the order of the words.

Three helpers, three jobs

lengths :: [String] -> [Int]
lengths = map length

longerThan :: Int -> String -> Bool
longerThan n word = length word > n

sumOf :: [Int] -> Int
sumOf = foldr (+) 0

One list, three helpers

Run it and check the line for the product by hand. Then write a helper that keeps numbers above 5 and use it to filter the same list.

Output

Click "Run" to execute your code

Notice how much of this chapter is a type: a function from a value to a Bool is exactly what a filter needs, and a function that takes two values of one type and answers one is exactly what a fold needs. When you can see the shape of the type, you can see which helper to reach for.

A fold replaces the colons

foldr is easier to read once you see what it replaces. A list is a : (b : (c : [])), and foldr f z swaps every colon for f and the empty list for z, giving f a (f b (f c z)). Nothing else happens.

That is why foldr (:) [] answers the list unchanged, why foldr (+) 0 is a sum, and why the starting value has to be the answer for an empty list. It is also why foldr is lazy in its second argument: f decides whether the rest is needed.

Helpers are arguments, so they compose

map, filter and foldr all take a function as an argument, which means the answer of one can be the input of the next. map shout (filter long items) reads from the inside out: keep the long words, then shout each one.

The types keep the pipeline honest. filter needs a function from a value to a Bool, and map needs a function from one value to another. If a helper has the wrong shape, the compiler says so where it is passed, not somewhere inside the walk.

all and any are the same idea folded into a Bool: all long items asks whether every value passes, and any asks whether one does. Both stop as soon as the answer is decided, which is the laziness of the fold showing through.

filter wants a test that answers a Bool, so filter length items is refused, because length answers a number. map and filter are not interchangeable: map keeps every value, so using it where you meant filter quietly keeps the ones you wanted to drop. And a fold starts from a value of the answer type, so foldr (+) 0 is a number while foldr (++) "" is text.

Try these next

Write oddOnly with filter and use it on the same list as small.
Use foldr to count how many values are above 5, starting from 0 and adding one for each.
Rewrite the joined line with concat and check it answers the same text.

A filter, a map and a fold in a row

Run it and read the six lines. Then add a `shorterThan` test, use it to keep the three-letter words, and check that the count changes.

Output

Click "Run" to execute your code

Check what you learned

One question at a time. A wrong answer explains itself — take another go.

Part 1 of 5

What does map double [1, 2, 3] answer, when double turns a number into twice itself?