Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 38 ยท Higher-order Functions

map, filter and fold

Replace hand-written recursion with map, filter, foldl, foldr, andmap and ormap in Racket. Learn argument order, building pipelines and how fold generalizes list recursion.

In the recursion chapter you wrote functions that double every number, keep only the evens, and sum a list. They all had the same skeleton. Higher-order functions capture those skeletons once, so you only write the part that differs. map, filter and the folds are the three most useful ones, and they appear in every modern language. In this lesson you learn what each does, how their arguments are ordered in Racket, and how to chain them.

Run examples use the stand-in interpreter, whose versions of these functions match Racket's argument order.

map: transform every element

(map f lst) applies f to each element and returns a list of the results, in the same order:

RACKET
(map add1 '(1 2 3))                    ; '(2 3 4)
(map (lambda (s) (string-length s)) '("a" "bcd" "ef"))   ; '(1 3 2)
(map + '(1 2 3) '(10 20 30))           ; '(11 22 33)   two lists

It is the generalization of double-all from the last chapter: the part that differs (what to do to one element) became the argument f.

map

filter: keep what passes

(filter pred lst) keeps the elements for which pred returns a true value:

RACKET
(filter even? '(1 2 3 4 5 6))                   ; '(2 4 6)
(filter (lambda (s) (> (string-length s) 2)) '("a" "bcd" "efgh"))  ; '("bcd" "efgh")
(filter odd? '())                               ; '()

A predicate returns a boolean (or any value, where only #f means "reject"). Real Racket also has filter-not, remove, and partition to split one list into passing and failing parts.

filter

foldl and foldr: combine everything

A fold reduces a list to a single value by combining elements one at a time. It takes a combining function, a starting value (the accumulator's initial value), and the list.

RACKET
(foldl + 0 '(1 2 3 4))    ; 10
(foldl * 1 '(1 2 3 4))    ; 24

The combining function receives the current element first, then the accumulator: (proc element accumulator). Watch how the order matters for something that is not commutative, such as cons:

RACKET
(foldl cons '() '(1 2 3))   ; '(3 2 1)    each element is consed onto the front: reverses!
(foldr cons '() '(1 2 3))   ; '(1 2 3)    rebuilds the same list
  • foldl processes left to right, building the accumulator as it goes. It uses constant stack space.
  • foldr processes right to left: it behaves like the recursion (f (first lst) (foldr f init (rest lst))).
flowchart LR
    S["init: 0"] --> A["+ 1"] --> B["+ 2"] --> C["+ 3"] --> R["result: 6"]

foldl with +: the accumulator passes along the list.

foldl and foldr

For the two subtraction results, trace by hand: (foldl - 0 '(1 2 3)) computes (- 3 (- 2 (- 1 0))), which is 2. (foldr - 0 '(1 2 3)) computes (- 1 (- 2 (- 3 0))), which is also 2 (for three elements the two alternating sums happen to agree). With two elements they differ: (foldl - 0 '(1 2)) is 1 but (foldr - 0 '(1 2)) is -1.

Writing your own functions with fold

Many list functions are one-liners with a fold:

RACKET
(define (my-sum lst) (foldl + 0 lst))
(define (my-length lst) (foldl (lambda (x acc) (+ acc 1)) 0 lst))
(define (my-reverse lst) (foldl cons '() lst))
(define (my-map f lst) (foldr (lambda (x acc) (cons (f x) acc)) '() lst))
(define (my-filter p lst)
  (foldr (lambda (x acc) (if (p x) (cons x acc) acc)) '() lst))

That last pair shows why fold is "the universal list function": map and filter are special cases.

map and filter from fold

andmap and ormap

(andmap f lst) is true if f returns true for every element; (ormap f lst) is true if it does for some element:

RACKET
(andmap even? '(2 4 6))      ; #t
(andmap even? '(2 3 6))      ; #f
(ormap even? '(1 3 4))       ; #t
(ormap even? '())            ; #f

Pipelines

Real programs chain these. Read the code from the inside out, or break it into named steps with let*. Task: sum the squares of the odd numbers up to 10.

A pipeline

Racket also provides for/list, for/sum and for/fold loops that do the same jobs with different syntax; you will see them in the applications chapter.

When to use a fold versus a named recursion

Use map and filter whenever they say exactly what you mean: they are short and obviously correct. Use foldl when you reduce a list to one value. Write explicit recursion when the structure is unusual (several lists, early exit, trees), because those do not fit a fold neatly.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does (filter even? '(1 2 3 4)) return?

    filter keeps the elements for which the predicate is true.
  2. 2. In Racket, what arguments does the function given to foldl receive?

    Racket's foldl calls (proc element accumulator).
  3. 3. What does (foldl cons '() '(1 2 3)) return?

    Each element is consed onto the front of the accumulator, which reverses the list.
  4. 4. What does (ormap even? '()) return?

    There is no element for which the predicate is true, so ormap returns #f.

Summary

  • map transforms every element, filter keeps some, folds combine all into one value.
  • foldl goes left to right and calls (proc element acc); foldr recurses from the right.
  • map and filter can both be written with foldr.
  • andmap and ormap ask whether all or any elements pass.
  • Chain them into pipelines; name intermediate steps with let* when it helps.

Next: Function Composition and Currying