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.
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'sProtocoland 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.
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.
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))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.
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 holds one value of and one of (a tuple, a record, a data class). A sum type (also tagged union or variant) holds a value of or a value of , 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 values and bool | Colour has . Optional[X] is : 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 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.
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)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.
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:
defaults = {"currency": "KES", "tags": []}
order_a = dict(defaults) # a shallow copy...
order_a["tags"].append("gift")
print(defaults["tags"]) # ['gift'] -- the inner list was sharedPython 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.
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)appliesfto every element;filter(p, xs)keeps the elements for whichpis true;reduce(op, xs, initial)(infunctools) 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.
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 nowSome notes from practice:
- Comprehensions usually read better than
mapandfilterin Python, and are the more common idiom;mapwith a named function (map(str.strip, lines)) is fine. Explicit loops are better still when the logic has several steps. reduceis 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 argumentlambda i=i: ...). - Closures and objects are two ways to package state with behaviour.
make_counteris a one-method object. When a closure needs a second method, a class is usually clearer.
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:
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 *. hThere 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:
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 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.
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
1. Types and functional programming
Warm-upHumanHow many distinct values does the type Optional[tuple[bool, Literal["red", "green", "blue"]]] have?
2. Types and functional programming
CoreHumanCat 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?
3. Types and functional programming
CoreHumanWhat 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-upHumanWhich of these functions are pure? Select all that apply.
5. Types and functional programming
CoreComputationalThe 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, returnErr; if it is outside 1024–65535 (inclusive), returnErr; otherwise returnOk(port)with anint. Never raise.and_then(result, f): ifresultis anOk, returnf(result.value)(wherefitself returns aResult); if it is anErr, return it unchanged without callingf.
6. Types and functional programming
CoreComputationalWrite 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 tovalueleft to right:pipe(x, h, g, f) == f(g(h(x))).
With no functions, compose() is the identity function and pipe(x) returns x.
7. Types and functional programming
StretchComputationalWrite 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.)
Further reading and resources
- Python: typing — support for type hints
- mypy documentation
- Pyright documentation
- PEP 484 — Type HintsThe proposal that defined Python's type hints, in 2014.
- PEP 634 — Structural Pattern Matching: Specification
- Python: functools — higher-order functions and operations on callable objects
- The Rust Programming LanguageChapters 6 (enums and pattern matching) and 9 (error handling) cover Option and Result.
- OCaml documentation
- Haskell