Chapter 4Standard MLslides.en.pdf:216-220

Fold Operators

foldl, foldr, map, filter, mapcan

Def 1.28 — foldlDef 1.31 — foldr

Concept

The fold operators are the universal recursion patterns for lists. They capture the idea of combining a list into a single value by repeatedly applying a function.

foldl — left fold (Def 1.28, slides p.216):
Process from the LEFT. The accumulator starts as s and each element is combined on the LEFT side of the function.
foldl f s [x1, x2, x3] = f(x3, f(x2, f(x1, s)))

Visually (list at bottom, accumulator growing up):

Notice the list is consumed right-to-left but the function f gets (element, accumulator).

foldr — right fold (Def 1.31, slides p.218):
Process from the RIGHT. The element is on the LEFT side of f.
foldr f s [x1, x2, x3] = f(x1, f(x2, f(x3, s)))

When does the order matter?
- For commutative operations like + and *, foldl op+ 0 xs and foldr op+ 0 xs give the same answer.
- For non-commutative operations like :: (cons) or subtraction, the order matters a lot. foldl op:: nil xs reverses xs; foldr op:: nil xs copies xs.
- For short-circuit operations (e.g. orelse), foldl may skip work; foldr processes everything.

Classic example — reverse:
fun rev xs = foldl op:: nil xs;

Classic example — sum:
fun sum xs = foldl op+ 0 xs;

Classic example — list product (the exam mapcan):
fun mapcan_with (f, l) = foldl (fn (v, s) => s @ f v) nil l;
This is the exam-Pattern 2.3 solution: map a list-valued function over a list, then concatenate.

Animation — foldl evolution

Transcript — click a line to jump9 cues

0.0sfoldl (+) 0 [1, 2, 3, 4]
1.1sThe list [1,2,3,4] appears as four cells across the top.
2.6sBelow: an Accumulator box, currently holding 0.
3.6sThe update rule: new acc = acc + x.
4.8sStep 1: cell 1 highlighted; acc transforms from 0 to 1.
6.3sStep 2: cell 2 highlighted; acc becomes 1 + 2 = 3.
7.7sStep 3: cell 3 highlighted; acc becomes 3 + 3 = 6.
9.1sStep 4: cell 4 highlighted; acc becomes 6 + 4 = 10.
12.5sResult: 10. foldl scans left-to-right, threading state.

Mutual recursion

SML allows mutually recursive function declarations using the and keyword:


fun even 0 = true
  | even n = odd (n - 1)
and odd 0 = false
  | odd n = even (n - 1);

Both functions are defined in the same declaration; each can call the other. They share a single scope.

Trace of even 4:
1. even 4 → calls odd 3.
2. odd 3 → calls even 2.
3. even 2 → calls odd 1.
4. odd 1 → calls even 0.
5. even 0 → returns true.
6. Back-propagate: all return true.

So even 4 = true. ✓

Fibonacci sequence

The Fibonacci sequence is defined by:
- $F(0) = 0$
- $F(1) = 1$
- $F(n+2) = F(n+1) + F(n)$

A naive SML implementation:


fun fib 0 = 0
  | fib 1 = 1
  | fib n = fib (n - 1) + fib (n - 2);

Time complexity: $\Theta(\varphi^n)$ where $\varphi = (1+\sqrt{5})/2 \approx 1.618$ — exponential, because of repeated sub-computation.

Recursion tree for fib 5: the root has two children fib 4 and fib 3; each of those branches into two more. The total number of calls grows exponentially.

A linear-time version uses a tuple to carry two consecutive Fibonacci numbers:


fun fob 0 = (0, 1)
  | fob n =
      let val (a, b) = fob (n - 1)
      in (b, a + b) end;

fun fib_fast n = #1 (fob n);

fob n returns the pair (F(n), F(n+1)). The recursion is single-branched and linear: $\Theta(n)$ .

For large Fibonacci numbers, ordinary int overflows around F(45). SML's basis library provides IntInf for arbitrary-precision integers:


fun bigfob 0 = (IntInf.fromInt 0, IntInf.fromInt 1)
  | bigfob n =
      let val (a, b) = bigfob (n - 1)
      in (b, a + b) end;

fun bigfib n = #1 (bigfob n);

IntInf.fromInt lifts an int into IntInf.int, and arithmetic operations on IntInf.int are unbounded.

Worked example

Step 0 of 2

Practice — score 100% to advance

Multiple choice

Per Def 1.28, what is foldl f s [x1, x2, x3]?

What does foldl op:: nil [1, 2, 3] evaluate to?

What does foldr op:: nil [1, 2, 3] evaluate to?

When does foldl vs foldr matter?

What does foldl op+ 0 [10, 20, 30] evaluate to?

In the exam's mapcan, what does this implementation do: foldl (fn (v, s) => s @ f v) nil l?

What are the two arguments foldl takes BEFORE the list?

The naive fib n = fib(n-1) + fib(n-2) has time complexity:

Fill in the blank

In SML, the ___ keyword introduces a mutually recursive function group.

Loading…