Functional programming II: recursion, immutability, laziness and pattern matching

Lesson 2 showed how pure and higher-order functions replace many loops. This lesson completes the functional toolkit. Without mutable loop counters, repetition is expressed by recursion. Without in-place updates, data is immutable, and new versions share structure with old ones. Laziness delays computation until a value is needed, which allows infinite sequences and avoids wasted work. Algebraic data types and pattern matching describe data as a fixed set of shapes and process each shape in its own case. Python supports all four ideas to some degree, and the comparison with Java and Rust shows how languages differ in how much they help.

Recursion instead of loops

A recursive function solves a problem by calling itself on smaller instances. You studied the proof side in CMPUT-272, where structural induction shows that a recursive definition is correct, and the cost side in CMPUT-204, where recurrences give running times. In functional programming, recursion is also the main control structure: where imperative code writes a loop that updates a variable, functional code writes a function whose result is defined in terms of the result on a smaller input.

def length(xs):                 # structural recursion on a list
    return 0 if not xs else 1 + length(xs[1:])

def total(tree):                # recursion on a nested structure
    """tree is a number or a list of trees"""
    if isinstance(tree, (int, float)):
        return tree
    return sum(total(t) for t in tree)

def flatten(tree):
    if not isinstance(tree, list):
        return [tree]
    return [x for t in tree for x in flatten(t)]

nested = [1, [2, 3, [4]], [[5], 6]]
print(length([7, 8, 9]), total(nested), flatten(nested))

3 21 [1, 2, 3, 4, 5, 6]

Each function has a base case for the smallest input and a recursive case that reduces the problem. The shape of the code mirrors the shape of the data: a list is empty or an element followed by a list, and a tree is a leaf or a list of trees. This correspondence between data definition and function definition is called structural recursion, and it is the most reliable way to write correct recursive functions.

Tail calls and the recursion limit

A call is a tail call when it is the last thing a function does, so its result is returned unchanged. Languages such as Scheme, Haskell and many ML dialects guarantee tail-call optimization: a tail call reuses the current stack frame, so a tail-recursive function runs in constant stack space, just like a loop. Python deliberately does not perform this optimization; its creator argued that full stack traces are more valuable for debugging. Every Python call uses a new frame, and the interpreter stops deep recursion with a `RecursionError` once the limit, 1,000 frames by default, is reached.

import sys

def count_down(n):          # tail-recursive in form
    if n == 0:
        return "done"
    return count_down(n - 1)

def count_down_loop(n):     # the loop a tail-call optimizer would produce
    while n != 0:
        n -= 1
    return "done"

print("limit:", sys.getrecursionlimit())
print(count_down(900))
try:
    count_down(5000)
except RecursionError as err:
    print("RecursionError:", err)
print(count_down_loop(5000))

limit: 1000
done
RecursionError: maximum recursion depth exceeded
done

The practical rule in Python is to use recursion for structures whose depth is small, such as trees, parsers and divide-and-conquer algorithms, where depth grows like \(\log n\), and to use loops or iterators for long linear sequences. Raising the limit with `sys.setrecursionlimit` only postpones the problem and can crash the interpreter if the C stack overflows. In a language with guaranteed tail calls, the recursive and loop versions above are equally efficient.

Immutability and persistent data

In functional programming, values do not change. Instead of updating a list in place, you build a new list. That sounds expensive, but immutable structures can share most of their contents. A persistent data structure keeps old versions available after an update, and a well-designed one copies only the parts that changed. A singly linked list is the simplest example: adding to the front creates one new node that points to the old list, and both versions remain valid.

from typing import NamedTuple, Optional

class Node(NamedTuple):              # an immutable list cell
    head: int
    tail: Optional["Node"]

def cons(x, xs): return Node(x, xs)

def to_list(xs):
    out = []
    while xs is not None:
        out.append(xs.head); xs = xs.tail
    return out

a = cons(3, cons(2, cons(1, None)))
b = cons(4, a)                       # new version shares all of a
print(to_list(a), to_list(b), "shared:", b.tail is a)

t = (1, 2, 3)
try:
    t[0] = 99
except TypeError as err:
    print("TypeError:", err)
fs = frozenset({"red", "green"}) | {"blue"}   # set operations return new frozensets
print(sorted(fs))

[3, 2, 1] [4, 3, 2, 1] shared: True
TypeError: 'tuple' object does not support item assignment
['blue', 'green', 'red']

Python offers immutable built-ins, tuples, strings, frozensets and frozen dataclasses, but its lists and dictionaries are mutable. Copying a large list for every change costs \(\Theta(n)\) time, so efficient persistent vectors and maps use trees with high branching factors, giving updates in \(O(\log n)\) with very small constants. Clojure, Scala and Haskell build these in; in Python, third-party libraries provide them. The benefit of immutability is that a value you hold can never change under you, which removes a whole class of bugs and makes values safe to share between threads, as lesson 9 explains.

Laziness and generators

Strict, or eager, evaluation computes a value as soon as the expression is reached. Lazy evaluation delays it until the value is needed. Haskell is lazy by default; Python is eager but provides laziness through iterators and generators. A generator function uses `yield` to produce values one at a time, pausing between them. Generator expressions, `map`, `filter`, `zip` and the `itertools` module all produce lazy iterators, so you can describe large or even infinite sequences and compute only the part you use.

from itertools import count, islice, takewhile

def primes():
    """Infinite generator of primes by trial division against earlier primes."""
    found = []
    for n in count(2):
        if all(n % p for p in takewhile(lambda p: p * p <= n, found)):
            found.append(n)
            yield n

print("first 10 primes:", list(islice(primes(), 10)))

squares = (n * n for n in count(1))              # infinite, but nothing computed yet
big = next(s for s in squares if s > 2000)
print("first square over 2000:", big)

calls = 0
def costly(x):
    global calls; calls += 1
    return x * 10
lazy = map(costly, range(1_000_000))
print(next(lazy), next(lazy), "calls made:", calls)

first 10 primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
first square over 2000: 2025
0 10 calls made: 2

The last part shows the payoff: `map` over a million elements did only two calls because only two values were requested. Laziness turns a pipeline of transformations into a stream that flows one element at a time, using constant memory regardless of input size. It also has costs. Errors appear only when the value is finally demanded, which can be far from where the expression was written, and a lazy iterator can be consumed only once. Side effects inside lazy pipelines are especially confusing, because they happen at unpredictable times or not at all.

Algebraic data types and pattern matching

An algebraic data type defines a value as one of a fixed set of variants, each carrying its own fields. A shape might be a circle with a radius, a rectangle with a width and height, or a triangle with three side lengths. Functions on such data examine which variant they have and handle each case. Pattern matching makes this concise: a match statement checks the shape of a value and binds its fields to names in one step. ML and Haskell introduced the idea; Rust has `enum` and `match`; Java added sealed interfaces, records and pattern matching for switch in Java 21; Python added the `match` statement in version 3.10.

from dataclasses import dataclass
import math

@dataclass(frozen=True)
class Circle:   r: float
@dataclass(frozen=True)
class Rect:     w: float; h: float
@dataclass(frozen=True)
class Tri:      a: float; b: float; c: float

def area(s):
    match s:
        case Circle(r):
            return math.pi * r * r
        case Rect(w, h) if w == h:
            return w * w                      # a guard picks out squares
        case Rect(w, h):
            return w * h
        case Tri(a, b, c):
            p = (a + b + c) / 2               # Heron's formula
            return math.sqrt(p * (p - a) * (p - b) * (p - c))
        case _:
            raise ValueError(f"unknown shape {s!r}")

for s in [Circle(1), Rect(2, 2), Rect(2, 5), Tri(3, 4, 5)]:
    print(f"{s!r:<26} area = {area(s):.3f}")

Circle(r=1)                area = 3.142
Rect(w=2, h=2)             area = 4.000
Rect(w=2, h=5)             area = 10.000
Tri(a=3, b=4, c=5)         area = 6.000

Python's `match` works on dataclasses because they define `__match_args__`, the order of fields for positional patterns. Patterns can also match literals, sequences such as `[first, *rest]`, and dictionaries such as `{'type': 'click', 'x': x}`, which makes `match` useful for processing JSON-like messages. Python does not check that every variant is handled; if you forget `Tri`, the program fails only when a triangle arrives. Rust checks exhaustiveness at compile time, as the next example shows.

enum Shape {
    Circle { r: f64 },
    Rect { w: f64, h: f64 },
    Tri { a: f64, b: f64, c: f64 },
}

fn area(s: &Shape) -> f64 {
    match s {
        Shape::Circle { r } => std::f64::consts::PI * r * r,
        Shape::Rect { w, h } => w * h,
        Shape::Tri { a, b, c } => {
            let p = (a + b + c) / 2.0;
            (p * (p - a) * (p - b) * (p - c)).sqrt()
        }
    }
}

fn main() {
    let shapes = vec![
        Shape::Circle { r: 1.0 },
        Shape::Rect { w: 2.0, h: 5.0 },
        Shape::Tri { a: 3.0, b: 4.0, c: 5.0 },
    ];
    let total: f64 = shapes.iter().map(area).sum();
    for s in &shapes {
        println!("area = {:.3}", area(s));
    }
    println!("total = {:.3}", total);
}

area = 3.142
area = 10.000
area = 6.000
total = 19.142

If you delete the `Tri` arm from the Rust `match`, the compiler refuses to build the program and reports that the pattern for triangles is not covered. Exhaustiveness checking turns a run-time surprise into a compile-time error. This is one of the clearest examples of a type system preventing a bug, and lesson 7 builds on it.