How do map, filter and fold replace loops?
Map, filter and fold are three functions that do the job of most loops over a list. Map changes every item, filter keeps some of the items, and fold boils a list down to one value.
They matter because three short words can replace a long loop, and you can read what each one does at a glance. In this lesson you apply them to the prices in a shop.
By the end of this lesson
Note
I can replace a loop over a list with map, filter or fold.
Key words
| Word | What it means |
|---|---|
| Map | apply a function to every item of a list |
| Filter | keep only the items that pass a test |
| Fold | combine all the items of a list into one value |
| Higher-order function | a function that takes another function as an argument |
| Accumulator | the running result that a fold carries along |
The cells students fill in are left blank in this preview.
Map applies a function to every item
A shop adds a 50 pence delivery fee to each price. In a loop you make a new list and add each answer to it. With map you say just two things: which function, and which list.
The part (+ 50) is a function waiting for one number. It adds 50 to whatever it is given. Map hands it every price in turn.
Try it: the loop that map replaces
def add_fee(price):
return price + 50
prices = [1000, 2500, 400]
with_fee = []
for price in prices:
with_fee.append(add_fee(price))
print(with_fee)
# Change add_fee so that it takes 10 off instead.
# Press Run. The loop stayed the same, only the function changed.
Add 50 to every price with map
docker exec haskell ghc -e "map (+ 50) [1000, 2500, 400]"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Ask GHC for the type of map
docker exec haskell ghc -e ":type map"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Filter keeps the items that pass a test
Now the shop wants only the prices above 500. The test (> 500) is a function that answers True or False. Filter keeps the items for which the test says True.
The answer can be shorter than the list you gave. If nothing passes, it is the empty list.
Keep the prices above 500
docker exec haskell ghc -e "filter (> 500) [1000, 250, 700, 90]"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Keep the even numbers
docker exec haskell ghc -e "filter even [1, 2, 3, 4, 5, 6]"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Fold combines a list into one value
A fold walks along a list and carries a running result, the accumulator. You give it three things: a function that combines two values, a start value, and the list.
foldr (+) 0 [10, 20, 30] starts at 0 and adds the items. The start value is also the answer for an empty list.
Add up three prices with a fold
docker exec haskell ghc -e "foldr (+) 0 [10, 20, 30]"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Find the biggest price with a fold
docker exec haskell ghc -e "foldr max 0 [3, 9, 4]"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Worked example: foldl and foldr with minus
| Call | How it is worked out | Answer |
|---|---|---|
| foldl (-) 100 [10, 20] | (100 - 10) - 20, from the left | 70 |
| foldr (-) 100 [10, 20] | 10 - (20 - 100), from the right | 90 |
| foldl (+) 0 [10, 20] | (0 + 10) + 20 | 30 |
| foldr (+) 0 [10, 20] | 10 + (20 + 0) | 30 |
The cells students fill in are left blank in this preview.
Fold minus from the left
docker exec haskell ghc -e "foldl (-) 100 [10, 20]"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Fold minus from the right
docker exec haskell ghc -e "foldr (-) 100 [10, 20]"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Filter, then map, then fold
docker exec haskell ghc -e "sum (map (* 2) (filter (> 500) [1000, 250, 700, 90]))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think foldl and foldr always give the same answer. They do for plus and times, where the order does not matter. They differ for minus, because 100 - 10 - 20 is not the same as 10 - (20 - 100).