Map, Filter, and Reduce (Fold)

Map, filter and reduce (called fold in Haskell) are the three workhorse higher-order functions of functional programming. Between them they cover the overwhelming majority of list processing: map transforms every element, filter selects elements, and fold combines elements into a single result. Crucially they replace the explicit loops of imperative code — and the AQA exam expects you to be able to trace their evaluation step by step, which is exactly what this lesson drills.

---

Spec Mapping

This lesson covers AQA 7517 §4.12.3 (using map, filter and fold/reduce on lists), building directly on the higher-order function ideas of §4.12.2. You must be able to: state what each function does and its effect on list length; read and write their Haskell type signatures; trace a reduction of each by substitution; explain the difference between foldr and foldl; and combine all three into a processing pipeline. These functions are the conceptual heart of the MapReduce programming model used for big data (§4.11).

The descriptions below restate the assessable content in our own words rather than quoting AQA's specification text.

---

Map

map applies a given function to every element of a list, producing a new list of the same length containing the transformed values.

Type signature and concept

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

It takes a function a -> b and a list of a, and returns a list of b. Mathematically:

$$\mathrm{map}\;f\;[x_1, x_2, \ldots, x_n] = [\,f(x_1),\; f(x_2),\; \ldots,\; f(x_n)\,]$$mapf[x1​,x2​,…,xn​]=[f(x1​),f(x2​),…,f(xn​)]

Haskell

doubled = map (*2) [1, 2, 3, 4, 5]
-- doubled = [2, 4, 6, 8, 10]

squares = map (^2) [1..5]
-- squares = [1, 4, 9, 16, 25]

import Data.Char (toUpper)
upper = map toUpper "hello"      -- a String is a list of Char
-- upper = "HELLO"

Traced evaluation of map (*2) [1,2,3]

map is defined recursively (you meet this in the list-processing lesson) as map f [] = [] and map f (x:xs) = f x : map f xs. Tracing by substitution:

  map (*2) [1, 2, 3]
= (*2) 1 : map (*2) [2, 3]
= 2 : ((*2) 2 : map (*2) [3])
= 2 : (4 : ((*2) 3 : map (*2) []))
= 2 : (4 : (6 : []))
= [2, 4, 6]

Key properties of map

• Output length equals input length (a one-to-one transformation).
• The order of elements is preserved.
• Each element is transformed independently — the function never sees its neighbours, which is exactly why map parallelises trivially.

Map can change the element type

A subtle but important point: map :: (a -> b) -> [a] -> [b] allows a and b to differ, so map can transform a list into one of a different element type. For instance, mapping show (which converts to a String) over a list of integers produces a list of strings:

labels = map show [1, 2, 3]      -- ["1", "2", "3"]  ::  [String]
lengths = map length ["hi", "hello", "yo"]   -- [2, 5, 2]  ::  [Int]

The length stays the same, but [Int] becomes [String] in the first case and [String] becomes [Int] in the second. This is why the signature uses two type variables a and b rather than one — map transforms values, and that may include changing their type.

Python contrast

celsius = [0, 20, 37, 100]
fahrenheit = list(map(lambda c: c * 9/5 + 32, celsius))
# fahrenheit = [32.0, 68.0, 98.6, 212.0]

---

Filter

filter keeps only the elements of a list that satisfy a predicate — a function returning Bool. The result is a new list that is the same length or shorter.

Type signature and concept

filter :: (a -> Bool) -> [a] -> [a]

Note the result type is [a], the same element type as the input — filter never changes elements, it only includes or excludes them.

$$\mathrm{filter}\;p\;[x_1, \ldots, x_n] = [\,x_i \mid p(x_i) = \mathrm{True}\,]$$filterp[x1​,…,xn​]=[xi​∣p(xi​)=True]

Haskell

evens = filter even [1..10]
-- evens = [2, 4, 6, 8, 10]

big = filter (>5) [1..10]
-- big = [6, 7, 8, 9, 10]

import Data.Char (isLower)
lowers = filter isLower "Hello World"
-- lowers = "elloorld"

Compound predicates

A predicate can combine several conditions with && (and) or logical OR, often most readably as a lambda. To keep numbers that are both even and greater than 5:

midEvens = filter (\x -> even x && x > 5) [1..12]
-- midEvens = [6, 8, 10, 12]

Only elements for which the whole Boolean expression is True survive: 2 and 4 are even but not over 5, so they are dropped; 7 and 9 are over 5 but odd, so they are dropped too. Building richer predicates this way lets a single filter express quite specific selection rules.

Traced evaluation of filter even [1,2,3,4]

The recursive definition keeps the head when the predicate holds and drops it otherwise:

  filter even [1, 2, 3, 4]
-- even 1 = False -> drop 1
= filter even [2, 3, 4]
-- even 2 = True  -> keep 2
= 2 : filter even [3, 4]
-- even 3 = False -> drop 3
= 2 : filter even [4]
-- even 4 = True  -> keep 4
= 2 : (4 : filter even [])
= 2 : (4 : [])
= [2, 4]

Key properties of filter

• Output length is less than or equal to input length.
• The order of surviving elements is preserved.
• Elements are never modified — only included or excluded.

map and filter together — a worked scenario

These two are frequently paired: filter to select, then map to transform. Suppose a list of prices in pounds is held and we want the prices over £20, each increased by 10% VAT-style surcharge:

prices = [12.0, 25.0, 8.0, 40.0, 19.0]

-- keep the expensive ones, then add 10%
result = map (* 1.1) (filter (> 20) prices)

Tracing the two stages:

  map (* 1.1) (filter (> 20) prices)
= map (* 1.1) [25.0, 40.0]      -- filter keeps prices over 20
= [25.0 * 1.1, 40.0 * 1.1]      -- map applies (* 1.1) to each
= [27.5, 44.0]

Order matters: filter first means we only do the multiplication on the values we actually keep. Doing filter (> 20) (map (* 1.1) prices) instead would test the already-surcharged prices against 20, changing which elements survive — a subtle bug worth noticing.

A reminder that strings are lists

Because a Haskell String is just [Char], map and filter work on text directly:

import Data.Char (toUpper, isLetter)

shout = map toUpper "hello, world!"        -- "HELLO, WORLD!"
letters = filter isLetter "h3ll0 w0rld"    -- "hllwrld"

No special string library is needed — the same two list functions cover text processing as well as numeric work.

---

Reduce (Fold)

fold (called reduce in Python and many other languages) collapses an entire list into a single value by repeatedly applying a binary combining function, starting from an initial accumulator. Where map and filter produce a list, fold produces one result — it is the operation you reach for whenever the answer is a total, a count, a maximum, a yes/no, or any other single summary of the whole list. The accumulator carries the "running answer" from one element to the next, which is how a fold replaces the mutable accumulator variable of an imperative loop. Haskell provides two directions, distinguished by which end of the list the nesting starts from.

foldr and foldl — type signatures

foldr :: (a -> b -> b) -> b -> [a] -> b   -- folds from the RIGHT
foldl :: (b -> a -> b) -> b -> [a] -> b   -- folds from the LEFT

Each takes the combining function, the initial accumulator, and the list.

The bracketing — this is the key idea

foldr associates to the right, nesting from the end of the list inward; foldl associates to the left, nesting from the start:

$$\mathrm{foldr}\;f\;z\;[a, b, c] = f\;a\;(f\;b\;(f\;c\;z))$$foldrfz[a,b,c]=fa(fb(fcz)) $$\mathrm{foldl}\;f\;z\;[a, b, c] = f\;(f\;(f\;z\;a)\;b)\;c$$foldlfz[a,b,c]=f(f(fza)b)c

Traced evaluation — sum with foldr

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

Traced evaluation — sum with foldl

  foldl (+) 0 [1, 2, 3]
= foldl (+) (0 + 1) [2, 3]
= foldl (+) ((0 + 1) + 2) [3]
= foldl (+) (((0 + 1) + 2) + 3) []
= ((0 + 1) + 2) + 3
= (1 + 2) + 3
= 3 + 3
= 6

Notice the opposite nesting: foldr builds 1 + (2 + (3 + 0)) while foldl builds ((0 + 1) + 2) + 3.

foldl vs foldr — when does it matter?

product = foldl (*) 1 [1, 2, 3, 4, 5]   -- 120

words   = ["Hello", " ", "World", "!"]
sentence = foldr (++) "" words           -- "Hello World!"

Fold	Direction	Bracketing for [a, b, c]
foldl	left → right	f (f (f z a) b) c
foldr	right → left	f a (f b (f c z))

For an operation that is associative and commutative (like + or *) the two folds give the same answer. For a non-commutative operation (like subtraction) they differ:

foldl (-) 10 [1, 2, 3]
-- = ((10 - 1) - 2) - 3 = 4

foldr (-) 10 [1, 2, 3]
-- = 1 - (2 - (3 - 10)) = 1 - (2 - (-7)) = 1 - 9 = -8

So whenever order matters, state which fold you mean — the marks depend on it.

Python contrast

from functools import reduce
total   = reduce(lambda acc, x: acc + x, [1, 2, 3, 4, 5], 0)   # 15
product = reduce(lambda acc, x: acc * x, [1, 2, 3, 4, 5], 1)   # 120

Python's functools.reduce is a left fold.

Choosing the starting value

A fold's initial accumulator is not arbitrary — it should be the identity element of the combining operation, the value that leaves the result unchanged. Get this wrong and the answer is wrong.

Operation	Correct starting value	Why
addition (+)	0	x + 0 = x
multiplication (*)	1	x * 1 = x
string/list join (++)	"" or []	joining with empty changes nothing
logical AND (&&)	True	x && True = x
logical OR	False	OR-ing with False changes nothing

For example, foldr (*) 0 [1,2,3] would give 0, not 6, because the stray 0 annihilates the product. Using 1 (the multiplicative identity) gives the intended 6. When summing a list of marks you seed with 0; when concatenating strings you seed with "".

A performance note — foldl versus foldl'

Because Haskell is lazy, a plain foldl does not actually add as it goes — it builds an ever-growing unevaluated expression ((0 + 1) + 2) + 3 + ... that is only computed at the very end. For a very long list this chain of deferred additions (called thunks) can consume a lot of memory and even overflow. The strict variant foldl' (from Data.List) forces each step immediately, using constant space:

import Data.List (foldl')
total = foldl' (+) 0 [1..1000000]   -- strict: evaluated as it goes, no thunk build-up

You will not be penalised for writing foldl in most exam answers, but knowing why foldl' exists — laziness interacting with folds — is exactly the kind of detail that lifts an evaluation answer into the top band.

---

Combining Map, Filter and Reduce — a Pipeline

The real power emerges when you chain the three: filter to select, map to transform, fold to summarise.

Example: sum of the squares of the even numbers in [1..10]

result = foldl (+) 0 (map (^2) (filter even [1..10]))
-- result = 220

The data flows through three stages, visualised below:

flowchart LR
    A["[1..10]"] -->|"filter even"| B["[2,4,6,8,10]"]
    B -->|"map (^2)"| C["[4,16,36,64,100]"]
    C -->|"foldl (+) 0"| D["220"]

Reading the pipeline stage by stage:

1. filter even [1..10] → [2, 4, 6, 8, 10] (selection — list shortens)
2. map (^2) → [4, 16, 36, 64, 100] (transformation — length unchanged)
3. foldl (+) 0 → 4 + 16 + 36 + 64 + 100 = 220 (combination — collapses to one value)

This filter → map → reduce shape is precisely the MapReduce pattern that distributes work across a cluster for big data (§4.11): the map/filter stages run in parallel on independent shards, and the fold stage combines the partial results.

A larger worked pipeline — order totals

Realistic problems stack the three functions to answer a question about structured data. Suppose each order is a pair (item, quantity) and we want the total revenue from orders of 3 or more items, where every item costs £5:

orders :: [(String, Int)]
orders = [("pen", 2), ("book", 5), ("mug", 3), ("pad", 1), ("lamp", 4)]