Skip to content
LumenaryAcademy
Engineering 80 min

Types and functional programming

Letting the computer check your reasoning, and programming with values and functions.

Code tested · 6AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

Why types, and why functions?

One of the most common crashes in Python programs is some version of AttributeError: 'NoneType' object has no attribute …: a value that was supposed to be there was not, and nothing noticed until that line ran with that input. The bug was knowable in advance — the function was declared, in effect, to sometimes return nothing — but the knowledge lived only in someone's head.

Types put that knowledge where a program can check it. A type checker reads your code before it runs and proves that certain mistakes cannot happen on any input: calling a method a value does not have, passing a string where a number is needed, forgetting that a lookup can fail. Types are also documentation that cannot go stale, and the foundation of every refactoring and autocompletion tool in your editor.

Functional programming is a style built on two ideas that pair naturally with types: compute with values that do not change, using functions with no side effects, and build bigger functions from smaller ones. You have already met its practical payoff in Designing programs: a functional core is easy to test and to reason about. This lesson gives you the vocabulary and the tools — in Python, which supports both ideas well, with a glimpse of the languages that build them in from the start.

DefinitionsH

Static, dynamic, strong, weak

Definition— Type, static and dynamic checking

A type is a set of values together with the operations allowed on them. Static type checking verifies, before the program runs, that every operation will be applied to values of a suitable type; dynamic checking performs the same verification while the program runs, at each operation.

Python is dynamically typed: len(42) is accepted when the file is loaded and fails only when that line executes. Java, Rust, Haskell, Go and TypeScript check statically. Note what "dynamic" does not mean: Python values certainly have types (type(42) is int), and the runtime enforces them.

A separate axis is strong versus weak typing, meaning how willing the language is to convert values implicitly. JavaScript evaluates "1" + 1 to "11" by converting the number to a string; Python raises TypeError. Python is dynamic and fairly strong; C is static and fairly weak (it converts between integer types and pointers readily). These terms are informal, so use them with care.

Two more distinctions you will meet:

  • Nominal versus structural. In a nominal system a type is compatible with another only if it is declared so (class Dog(Animal)). In a structural one, any value with the right shape will do. Python's Protocol and TypeScript's interfaces are structural, which matches Python's duck typing.
  • Soundness. A sound checker never accepts a program that can go wrong at runtime in the ways it promises to rule out. Most practical checkers for dynamic languages are deliberately unsound in places (Any, casts, unchecked code) to stay usable. A passing type check is strong evidence, not proof.

Python and TypeScript use gradual typing: annotations are optional, unannotated code is treated leniently, and a codebase can adopt types one module at a time.

ComputationC

Type hints and checkers

Python's type hints (PEP 484) annotate parameters, return values and variables. CPython itself does not enforce them: they are stored as data and ignored when the code runs. Separate tools — mypy and Pyright are the most widely used — read the annotations and check the whole program statically, usually in your editor and in continuous integration.

python
from typing import Optional, Sequence, TypeVar, get_type_hints

T = TypeVar("T")

def first(items: Sequence[T]) -> Optional[T]:
    """The first item, or None for an empty sequence. Generic: works for any item type T."""
    return items[0] if items else None

def shout(name: str) -> str:
    return name.upper() + "!"

print(first(["Lagos", "Lima"]), first([]))
print(get_type_hints(shout))        # the annotations are data the program can inspect...

try:
    print(shout(42))                # ...but CPython does not check them at the call
except AttributeError as err:
    print("fails only when the line runs:", err)

city = first(["Quito", "Accra"])    # a checker infers Optional[str] here
if city is not None:                # narrowing: inside this branch, city is str
    print(shout(city))
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Run a checker over that file and it reports two things before anything executes: that shout(42) passes an int where a str is expected, and — if you delete the if city is not None test — that city might be None, where shout requires a str. That second check alone rules out the whole class of crash described at the start of this lesson. Checkers understand narrowing: after if city is not None, or isinstance(x, str), or an early return, they know the more precise type in the branch that follows.

Generics

first is generic: the type variable T says "whatever type of item goes in, the same type (or None) comes out", so first(["Lagos"]) has type Optional[str] and first([1, 2]) has type Optional[int]. Container types are generic too: list[int], dict[str, list[float]]. (Python 3.12 added a shorter syntax, def first[T](items: Sequence[T]) -> T | None; the TypeVar form above works on every current version.)

Generic containers raise a subtle question called variance. If Dog is a subtype of Animal, is list[Dog] a subtype of list[Animal]? It must not be: a function that accepts list[Animal] may append a Cat, and then your list of dogs contains a cat. So list is invariant. A read-only Sequence[Dog], on the other hand, can safely be used as a Sequence[Animal], since nothing can be added through it: Sequence is covariant. The practical rule is to annotate parameters with the most general read-only type you need (Sequence, Mapping, Iterable) rather than list or dict.

Adopting types in practice

On a real codebase, teams usually start by type-checking new code, annotate public interfaces first (where types document the most), enable stricter options module by module (mypy's --strict, Pyright's "strict" mode), and treat Any and # type: ignore like any other code smell: allowed, but explained. Third-party libraries ship their own annotations or have stubs in the shared typeshed project.

DefinitionsH

Algebraic data types

Most data has one of two shapes. Either it is this and that — a reading has a station and a temperature — or it is this or that — an order is placed or shipped or delivered or cancelled. Type theory calls these product and sum types; together, built up recursively, they are algebraic data types.

Definition— Product and sum types

A product type A×BA \times B holds one value of AA and one of BB (a tuple, a record, a data class). A sum type A+BA + B (also tagged union or variant) holds a value of AA or a value of BB, together with a tag saying which.

The names come from counting. If bool has 2 values and Colour = Literal["red", "green", "blue"] has 3, then tuple[bool, Colour] has 2×3=62 \times 3 = 6 values and bool | Colour has 2+3=52 + 3 = 5. Optional[X] is X+1X + 1: every value of X, plus None. The arithmetic is more than a pun — products and sums are characterised by universal properties, as Products by maps explains — and it gives a precise way to compare designs.

Suppose an order were modelled as one class with optional fields: status: str, tracking: Optional[str], signed_by: Optional[str], cancel_reason: Optional[str]. Even with only four allowed statuses, that is 4×2×2×2=324 \times 2 \times 2 \times 2 = 32 shapes, of which four are meaningful. Every function that receives an order must defend against the other 28: a "placed" order with a signature, a "cancelled" order with no reason. A sum type has exactly the four meaningful shapes, so the impossible ones cannot be constructed — the maxim is make illegal states unrepresentable. In Python: one frozen data class per case, a Union of them, and structural pattern matching to take them apart.

python
from dataclasses import dataclass
from typing import NoReturn, Union

@dataclass(frozen=True)
class Placed:
    pass

@dataclass(frozen=True)
class Shipped:
    tracking: str

@dataclass(frozen=True)
class Delivered:
    tracking: str
    signed_by: str

@dataclass(frozen=True)
class Cancelled:
    reason: str

OrderState = Union[Placed, Shipped, Delivered, Cancelled]     # a sum of four products

def assert_never(value: NoReturn) -> NoReturn:                 # typing.assert_never in 3.11+
    raise AssertionError(f"unhandled case: {value!r}")

def describe(state: OrderState) -> str:
    match state:
        case Placed():
            return "placed, waiting to be shipped"
        case Shipped(tracking):
            return f"on its way, tracking number {tracking}"
        case Delivered(signed_by=who):
            return f"delivered, signed for by {who}"
        case Cancelled(reason):
            return f"cancelled ({reason})"
        case _:
            assert_never(state)

def ship(state: OrderState, tracking: str) -> OrderState:
    if not isinstance(state, Placed):
        raise ValueError(f"cannot ship an order that is {describe(state)}")
    return Shipped(tracking)

def deliver(state: OrderState, signed_by: str) -> OrderState:
    if not isinstance(state, Shipped):
        raise ValueError(f"cannot deliver an order that is {describe(state)}")
    return Delivered(state.tracking, signed_by)

history: list[OrderState] = [Placed()]
history.append(ship(history[-1], "KE-4471-NBO"))
history.append(deliver(history[-1], "Achieng"))
for state in history:
    print(describe(state))

try:
    ship(Cancelled("customer request"), "XX-1")
except ValueError as err:
    print("rejected:", err)
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Two things make this robust. Each state carries only the data that exists in that state — you cannot ask a Placed order for its tracking number, because it has none. And the checker knows the four cases: the assert_never call in the fallback branch type-checks only if every case above it has been handled, so adding a fifth state (Returned) makes mypy or Pyright point at every match that forgot it. In languages with built-in sum types, as we will see, that exhaustiveness check is automatic.

IntuitionH

Immutability and pure functions

Definition— Pure function

A function is pure if its result depends only on its arguments, and calling it has no observable effect besides returning that result: it does not modify its arguments or any global state, perform input or output, or read the clock or a random generator.

A call to a pure function can be replaced by its value without changing the program — referential transparency — which is what makes such code easy to reason about: to understand total(prices) you read total and nothing else. Pure functions are trivially testable, safe to cache (memoise), and safe to run in parallel, because there is no shared state to race on (the hazard Concurrency spent a whole lesson on).

Purity is easiest with immutable data. Mutable data shared between two names is the source of a classic family of bugs:

python
defaults = {"currency": "KES", "tags": []}
order_a = dict(defaults)                 # a shallow copy...
order_a["tags"].append("gift")
print(defaults["tags"])                  # ['gift'] -- the inner list was shared

Python offers immutable building blocks — tuple, frozenset, strings and numbers, frozen data classes — and dataclasses.replace(order, status="shipped") produces a modified copy of a frozen object instead of changing it in place. Python does not enforce immutability deeply (a frozen data class can hold a list), so it remains partly a matter of discipline.

Functional programming does not abolish state and effects; programs exist to have effects. It pushes them to the edges, exactly as the functional-core/imperative-shell pattern does, so that most of the code is pure and the effectful part is small and obvious.

ComputationC

Higher-order functions and closures

In Python, functions are values: you can pass them as arguments, return them from functions and store them in data structures. A higher-order function takes or returns functions. You have used several already — sorted(items, key=...), max(..., key=...) — and three classic ones come from the functional tradition:

  • map(f, xs) applies f to every element;
  • filter(p, xs) keeps the elements for which p is true;
  • reduce(op, xs, initial) (in functools) folds the elements into one value: op(op(op(initial, x1), x2), x3).

A closure is a function that remembers variables from the scope where it was created, even after that scope has finished.

python
from functools import partial, reduce
import operator

prices_cents = [1250, 899, 4500, 120, 3999]

with_vat = list(map(lambda p: round(p * 1.16), prices_cents))       # 16% VAT
large = list(filter(lambda p: p >= 1000, with_vat))
total = reduce(operator.add, large, 0)
print(with_vat, large, total)
# The same pipeline as a Python programmer would usually write it:
print(sum(p for p in (round(c * 1.16) for c in prices_cents) if p >= 1000))

def compose(*fns):
    """compose(f, g, h)(x) == f(g(h(x))): functions in, a function out."""
    return reduce(lambda f, g: lambda x: f(g(x)), fns, lambda x: x)

slugify = compose("-".join, str.split, str.lower, str.strip)
print(slugify("  Café de Flore  Opening Hours "))

def make_counter(start=0):
    count = start
    def next_number():
        nonlocal count                 # rebind the enclosing variable, not a new local
        count += 1
        return count
    return next_number

ticket = make_counter(100)
print(ticket(), ticket(), ticket())

# The late-binding trap: a closure captures the *variable*, not its value at creation.
greeters = [lambda: f"table {i}" for i in range(3)]
print([g() for g in greeters])                       # every one sees the final i
greeters = [partial(lambda n: f"table {n}", i) for i in range(3)]
print([g() for g in greeters])                       # partial binds the value now
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Some notes from practice:

  • Comprehensions usually read better than map and filter in Python, and are the more common idiom; map with a named function (map(str.strip, lines)) is fine. Explicit loops are better still when the logic has several steps.
  • reduce is clearest with a named, associative operation — operator.add, max, set union. An associative operation with an identity element forms a monoid (see Algebraic structures), and associativity is exactly what lets a reduction be split across many machines and combined afterwards, the principle behind batch and stream processing frameworks.
  • The late-binding trap is real and appears in callbacks, event handlers and loops that build tasks. Bind the value explicitly (functools.partial, or a default argument lambda i=i: ...).
  • Closures and objects are two ways to package state with behaviour. make_counter is a one-method object. When a closure needs a second method, a class is usually clearer.
ExplanationH

A glimpse of Haskell, OCaml and Rust

The ideas in this lesson are optional in Python. In the ML family of languages (Standard ML, OCaml, F#), in Haskell and, more recently, in Rust, they are built in, and the result is a distinctive way of programming.

Sum types and exhaustive matching are native. In OCaml, a type with several cases is one declaration, and the compiler warns about any match that misses a case:

text
type shape = Circle of float | Rect of float * float

let area s = match s with
  | Circle r -> 3.14159 *. r *. r
  | Rect (w, h) -> w *. h

There is no null. Instead, a value that may be absent has an option type — Option in Rust, Maybe in Haskell — a sum type with two cases, Some(value) or None (in Haskell, Just value or Nothing). Because an optional user is not a User, the compiler will not let you call a User method on it until you have matched on both cases. Tony Hoare, who introduced the null reference in 1965, later called it his "billion-dollar mistake"; Option is the fix, and Python's Optional plus a type checker is a retrofitted version of it.

Errors are values. Rust functions that can fail return a Result, generic in the type of the value and of the error: either Ok(value) or Err(error). The caller must handle both; the ? operator propagates an Err upwards in one character, which keeps the happy path readable:

rust
fn read_port(text: &str) -> Result<u16, String> {
    let port: u16 = text.trim().parse().map_err(|e| format!("bad port {text:?}: {e}"))?;
    if port < 1024 {
        return Err(format!("port {port} is reserved"));
    }
    Ok(port)
}

Compared with exceptions, Result makes every failure visible in a function's type, so a reader and the compiler both know which calls can fail. The cost is some verbosity, which ? and combinators like map and and_then keep small.

Types are inferred. Haskell and OCaml programs often contain almost no type annotations, yet are fully statically typed: the Hindley–Milner algorithm infers the most general type of every expression. Rust and modern Java, C# and TypeScript infer types within functions. Static typing does not have to mean verbosity.

Purity can be enforced. Haskell separates pure functions from effectful ones in their types: a function that reads a file has a type mentioning IO, so purity is visible and checked. Most other languages, including OCaml and Rust, leave purity as a discipline, but make immutability the default (let bindings in Rust cannot be modified unless declared mut).

The theory behind all of this — the λ-calculus and type theory — is covered in Lumenary Math's The λ-calculus and Type theory and propositions as types; the second explains the remarkable fact that types can express logical propositions and programs can be proofs, which is how proof assistants such as Lean work.

Common misconceptionsH

Common misconceptions

Misconception

"Type hints make Python check types at runtime." CPython ignores annotations when running code. They are checked only by separate tools such as mypy and Pyright, or by libraries that choose to read them (pydantic, for example, validates data against them).

Misconception

"Dynamically typed means untyped." Every Python value has a type, and operations check it at runtime: "1" + 1 raises TypeError. The difference is when mistakes are found — when the line runs, possibly in production, versus before the program runs at all.

Misconception

"If the type checker passes, there are no type errors." Gradual checkers trust Any, casts, ignore comments and unannotated libraries. Types also say nothing about most logic errors: def average(xs: list[float]) -> float type-checks whether it divides by len(xs) or by len(xs) - 1. Types complement tests; they do not replace them.

Misconception

"Functional programming means no state and no effects." Useful programs read input, store data and send messages. Functional style isolates those effects and makes state changes explicit (a new value instead of a modified one), so that most of the code can be reasoned about in isolation.

History & global context

A short history

Alonzo Church's λ-calculus (1930s) described computation purely as function application, and Church also gave it a type system in 1940. John McCarthy's Lisp (1958) brought functions-as-values to practical programming. In the 1970s Robin Milner's ML, built as the language for a theorem prover at Edinburgh, combined static types with full type inference, using the algorithm now known as Hindley–Milner. A committee designed Haskell (1990) as a common, purely functional, lazily evaluated research language. Many of these ideas reached mainstream languages decades later: generics in Java (2004), lambdas in Java 8 (2014), Swift's and Kotlin's optionals, Rust (1.0 in 2015) with sum types and Result at its core, TypeScript's gradual types for JavaScript (2012), and Python's type hints (2014, with mypy, begun by Jukka Lehtosalo, as the first checker) and pattern matching (2021).

Exercises

Exercises

1. Types and functional programming

Warm-upHuman

How many distinct values does the type Optional[tuple[bool, Literal["red", "green", "blue"]]] have?

2. Types and functional programming

CoreHuman

Cat and Dog are subclasses of Animal. A type checker rejects passing a list[Dog] to def feed_all(animals: list[Animal]) -> None. Why, and what is the usual fix?

Choose one

3. Types and functional programming

CoreHuman

What does this print?

fs = [lambda: i * 10 for i in range(4)]
print(sum(f() for f in fs))

4. Types and functional programming

Warm-upHuman

Which of these functions are pure? Select all that apply.

Choose all that apply

5. Types and functional programming

CoreComputational

The starter defines a small Result type in the style of Rust: Ok(value) or Err(message). Write:

  • parse_port(text): strip surrounding whitespace; if the rest is not a decimal integer, return Err; if it is outside 1024–65535 (inclusive), return Err; otherwise return Ok(port) with an int. Never raise.
  • and_then(result, f): if result is an Ok, return f(result.value) (where f itself returns a Result); if it is an Err, return it unchanged without calling f.
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

6. Types and functional programming

CoreComputational

Write two higher-order helpers:

  • compose(*fns) returns a function that applies the functions right to left: compose(f, g, h)(x) == f(g(h(x))).
  • pipe(value, *fns) applies the functions to value left to right: pipe(x, h, g, f) == f(g(h(x))).

With no functions, compose() is the identity function and pipe(x) returns x.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Types and functional programming

StretchComputational

Write memoize(f), which returns a new function g that behaves like f (for hashable positional arguments) but remembers results: a second call with the same arguments returns the stored result without calling f. Keep the cache in a closure, not a global. Also give g an attribute g.misses counting how many times f was actually called.

(The standard library's functools.cache does this for real; build your own to see how.)

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Further reading and resources