Map, filter and fold

The three higher-order functions, foldl and foldr, and a pipeline over a log of sensor readings.

A13.5Functional programmingA level25 min

Covers AQA 7517 4.12.2.1 Functional language programs · Eduqas A500QS 1.4 Principles of programming

Print it: worksheet (PDF) · answers (PDF) · as a web page

Most of what a program does with a list is one of three things: change every item, keep some of the items, or combine all the items into one answer. At GCSE you wrote a loop for each. A functional language has a higher-order function for each instead, map, filter and fold (also called reduce), and you pass it the function that does the work. In this lesson you use all three on BugBot's sensor log.

The log

BugBot turned on the spot, taking a distance reading every 30 degrees and writing each one to a file. A reading of 400.0 means nothing was in range.

time,heading,cm
0.0,0,51.0
1.2,30,58.9
2.4,60,24.5
3.6,90,12.5
4.8,120,19.0
6.0,150,33.2
7.2,180,47.8
8.4,210,400.0
9.6,240,62.1
10.8,270,44.0
12.0,300,15.5
13.2,330,40.2

map: change every item

map takes a function and a list, applies the function to every item, and gives the list of results, in the same order. The new list is the same length as the old one.

cms = [51.0, 58.9, 24.5, 12.5]

print(list(map(lambda cm: cm * 10, cms)))       # to millimetres
print(list(map(round, cms)))                     # any one-argument function
print(list(map(str, [0, 30, 60])))

Run this in the simulator

In Haskell, map (*10) [51, 58, 24] is [510, 580, 240]. Its type shows it is higher-order:

map :: (a -> b) -> [a] -> [b]

Give it a function from a to b and a list of a, and it gives a list of b. Python's map gives back a map object that works the items out only when they are needed, so wrap it in list() or tuple() to see them all.

filter: keep some items

filter takes a predicate, a function that returns a Boolean, and a list. It gives a new list of exactly the items for which the predicate is true, in their original order. The original list is not changed.

cms = [51.0, 58.9, 24.5, 12.5, 400.0]

valid = list(filter(lambda cm: cm < 400, cms))
clear = list(filter(lambda cm: cm > 40, valid))
print(valid)
print(clear)

Run this in the simulator

In Haskell, filter (>40) [51, 24, 58] is [51, 58], and filter :: (a -> Bool) -> [a] -> [a].

fold: combine everything into one value

fold (reduce) reduces a list to a single value by repeatedly applying a combining function. It needs three things: a function of two arguments, a starting value, and the list. The function combines the answer so far with the next item.

from functools import reduce

cms = [3, 5, 2]
total = reduce(lambda so_far, cm: so_far + cm, cms, 0)
print(total)

Run this in the simulator

A trace of reduce(lambda a, b: a + b, [3, 5, 2], 0):

Haskell has two folds. foldl (fold left) starts at the left, as Python's reduce does. foldr (fold right) starts at the right:

foldl (+) 0 [3,5,2]    = ((0 + 3) + 5) + 2  = 10
foldr (+) 0 [3,5,2]    = 3 + (5 + (2 + 0))  = 10
foldl (-) 0 [1,2,3]    = ((0 - 1) - 2) - 3  = -6
foldr (-) 0 [1,2,3]    = 1 - (2 - (3 - 0))  = 2

For + the direction does not matter, but for a function like - it does. When a question asks for the result of a fold, write the brackets out as above before working it out.

A fold can build any single value, not only a number. Here it keeps whichever of two readings is nearer, so the value it builds is the nearest reading of all:

from functools import reduce

log = [(0, 51.0), (30, 58.9), (60, 24.5), (90, 12.5), (120, 19.0)]   # (heading, cm)
nearer = lambda a, b: a if a[1] <= b[1] else b
print(reduce(nearer, log))

Run this in the simulator

With no starting value, reduce starts with the first item as a. This prints (90, 12.5).

Putting them together

The three combine into a pipeline. Filter out bad readings, map each reading to what you need, fold to one answer:

from functools import reduce

log = [(0, 51.0), (30, 58.9), (60, 24.5), (90, 12.5), (210, 400.0), (240, 62.1)]

valid = list(filter(lambda r: r[1] < 400, log))
metres = list(map(lambda r: r[1] / 100, valid))
furthest = reduce(lambda a, b: a if a > b else b, metres)
print(len(valid), "valid readings, furthest", furthest, "m")

Run this in the simulator

Compare this with the loop you would have written at GCSE. There is no counter, no list that grows, and no variable that changes: each line makes a new value from the one before. That is what makes the pipeline easy to test stage by stage, and, as lesson A13.7 shows, easy to split across many computers.

Python can also write map and filter as a list comprehension: [r[1] / 100 for r in log if r[1] < 400] does the filter and the map at once. Comprehensions came to Python from functional languages; Haskell writes the same thing as [snd r / 100 | r <- readings, snd r < 400].

On the robot

The same three functions work on readings the robot takes right now. Taking the readings is the side effect, kept at the edge; everything after it is pure.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()
from functools import reduce

log = []
for i in range(8):
    log.append((i * 45, distance()))
    turn_right(30, angle=45)

clear = list(filter(lambda r: r[1] > 40, log))
headings = list(map(lambda r: r[0], clear))
nearest = reduce(lambda a, b: a if a[1] <= b[1] else b, log)
print("clear headings", headings)
print("nearest", nearest)

Run this in the simulator

Task: analyse the sweep

Analyse sweep.csv (above) with map, filter and fold. There must be no for or while anywhere in the program (so no comprehensions either), and no min, max or sum: use map, filter and reduce instead.

• parse(line) takes one line of the file, such as "2.4,60,24.5", and returns a tuple (time, heading, cm) with time a float, heading an int and cm a float.
• Read the file, skip the header line, and map parse over the rest.
• Keep only the valid readings, those under 400 cm, and print valid: <how many>.
• Of the valid readings, print the headings of those over 40 cm, in the order they are in the file, as clear: 0 30 ... separated by spaces.
• Fold the valid readings to find the nearest, and print nearest: <cm> cm at <heading>.
• Fold the valid readings to their total, and print mean: <mean cm> rounded to one decimal place.

The robot does not move.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()
from functools import reduce

f = open("sweep.csv", "r")
lines = f.read().splitlines()
f.close()

for line in lines[1:]:
    print(line)

Challenges

1. Write foldr (-) 0 [5,3,1] and foldl (-) 0 [5,3,1] with brackets, work out both, then check the left one with reduce.
2. Use one fold, and no len, to count how many valid readings are under 20 cm.
3. Write your own my_map(f, xs) and my_filter(p, xs) using recursion and no loops.