Foundations of Computer Science

Levels of abstraction

Large computer systems can only be understood by dividing them into levels of abstraction. Each level provides services to the level above it, implemented using services from the level below. The boundary between levels is the interface.

The interface must do two things:

• Supply the advertised services to the higher level
• Block access to the implementation details of the lower level

This abstraction barrier allows one level to be changed without affecting levels above. For example, when a manufacturer designs a faster processor, existing programs must continue to run — differences between old and new processors must be invisible to the program.

Recurring issues at every level:

• What services to provide at each level
• How to implement them using lower-level services
• The interface that defines how the two levels communicate

Example: dates

Inadequate internal formats have caused real crises:

• Digital PDP-10 (1975): Used 12-bit dates — good for at most 2^12 = 4096 days, or about 11 years
• Year 2000 crisis: Most industry formats used two-digit years (YYMMDD). The common “solution” was adding two further characters, altering file sizes. Yet the existing six characters already provide 48 bits — sufficient for the projected lifetime of the universe: 2^48 = 2.8 × 10^14 days ≈ 7.7 × 10^11 years

The lesson: mathematicians think in unbounded ranges, but computer representations impose hard limits. A good programming language lets you change the representation easily, but compatibility with old file formats remains a problem.

Example: floating-point numbers

A floating-point number is represented internally by two integers (mantissa and exponent). The concept of a data type involves:

• How a value is represented inside the computer
• The suite of operations given to programmers
• Valid and invalid (exceptional) results, such as “infinity”

Because of finite precision, floating-point computations are potentially inaccurate. For example, computing (2^1/10000)^10000 on a calculator may yield 1.99999959 rather than 2. Certain computations can cause errors to spiral out of control.

Floating-point numbers are an abstract type: the programmer uses operations like *. and +. without knowing the mantissa/exponent representation, and can change the underlying precision without rewriting code.

Data types and type safety

Inside the computer, all data are stored as bits. In most languages, the compiler uses types to generate correct machine code — types are not stored during program execution. Early languages like Fortran barred programmers from mixing types (INTEGER, REAL, COMPLEX). Modern languages handle many kinds of data including text and symbols, and the type system prevents senseless combinations at compile time.

What is programming for?

Programming describes a computation so it can be done mechanically. There are two fundamental building blocks:

• Expressions compute values (e.g., pi *. r *. r)
• Commands cause effects (e.g., assignment, input/output)

Programs should be:

• Correct — giving the right answers
• Efficient — giving answers quickly
• Modifiable — easy to change as requirements evolve

Programming-in-the-small vs in-the-large

Programming-in-the-small concerns writing code for simple, clearly defined tasks. Expressions describe mathematical formulae (this was the original contribution of FORTRAN, the FORmula TRANslator). Commands describe how control flows from one part of the program to the next.

Programming-in-the-large concerns joining large modules to solve complex, messy tasks. As we code layer upon layer, we need mechanisms for one part of the program to provide interfaces to other parts.

Modularity mechanisms

Three main approaches to modularity have emerged:

OCaml has a sophisticated module system that can do many of the same things as classes. OCaml also includes an object system, though it is less commonly used than its module system.

Why OCaml?

OCaml is chosen for this course because:

• Interactive: code can be tried immediately in a read-eval-print loop
• Flexible data types: a rich type system with type inference
• Safe: hides the underlying hardware — a program can abort but it cannot crash
• Mathematically tractable: programs can be designed and understood without thinking in detail about how the computer runs them
• Immutable by default: distinguishes naming something from updating memory
• Automatic memory management: manages storage for the programmer

OCaml occupies a sweet spot combining efficiency, expressiveness, and practicality. It descends from ML, the meta language of Robin Milner’s LCF proof assistant (1972). The modern OCaml emerged in 1996 and has since attracted significant commercial and academic use.

Correctness and efficiency

A correct program that runs too slowly is not useful. Conversely, a fast program that gives wrong answers is dangerous. Throughout this course, we study both:

• How to write programs whose correctness follows from their structure (recursion justified by mathematical induction)
• How to analyse and improve efficiency using Big O notation and techniques like tail recursion and reduction in strength

Value declarations

A let binding gives a name to a value:

let pi = 3.14159265358979
(* val pi : float = 3.14159265358979 *)

This is a value declaration. The name pi is an identifier. OCaml echoes the name, type (float), and value. Unlike variables in imperative languages, pi cannot be reassigned — its meaning persists even if a new let pi = ... is issued later.

Function declarations

A function encapsulates a computation so the formula does not need to be remembered:

let area r = pi *. r *. r
(* val area : float -> float = <fun> *)

area takes a float r and returns a float. The arrow -> in the type indicates a function. Calling a function does not require brackets:

area 2.0
(* - : float = 12.56637061435916 *)

Operators

Multiplication of floats uses *. (not *, which is for integers). This is an infix operator — written between its two operands. Integer multiplication uses *, integer addition uses +, float addition uses +..

Conditional expressions

OCaml uses if-then-else expressions, due to John McCarthy:

if true then x else y = x
if false then x else y = y

Evaluation: OCaml first evaluates the condition (of type bool). If the result is true, it evaluates the then branch; if false, the else branch. Crucially, only one branch is evaluated. If both were evaluated, recursive functions would run forever.

The condition is an expression of type bool, whose two values are true and false.

Relational operators

Tests between values use standard operators:

Equality testing with = is allowed provided both operands have the same type and equality is defined for that type.

Boolean operators

Boolean expressions can be combined:

New properties can be declared as functions:

let even n = n mod 2 = 0
(* val even : int -> bool = <fun> *)

Here mod computes the remainder of integer division.

int vs float

OCaml distinguishes strictly between integer and floating-point types:

The decimal point makes all the difference: 0 is an int; 0.0 is a float. OCaml will never automatically convert between them — this prevents subtle rounding errors.

Type constraints (annotations)

Although OCaml normally infers types, you can supply hints for debugging or to force a more specific type:

let square (x : float) = x *. x
(* val square : float -> float = <fun> *)

This constrains x to be float. Alternatively, constrain the result type:

let square x : float = x *. x
(* val square : float -> float = <fun> *)

Type constraints can appear almost anywhere in an expression.

Type inference

OCaml is unusual in that it infers types automatically. You rarely need to specify types explicitly. The compiler works out the most general type that an expression can have. For example, from x *. x it deduces x must be float because *. requires float operands.

Conversion functions

To mix integers and floats, explicit conversion is required:

int_of_float 3.14159   (* - : int = 3 *)
float_of_int 3         (* - : float = 3. *)

These conversion functions truncate (not round) when going from float to int.

Modules and compound identifiers

OCaml’s libraries are organised using modules. Functions from modules are accessed with compound identifiers using dot notation:

Float.of_int 3    (* equivalent to float_of_int *)
String.length "abc"
List.rev [1; 2; 3]

The module name acts as a namespace, preventing name clashes between different libraries. Thousands of library functions are available for text processing, operating system interaction, and numerical computation.

Why typed languages?

Some languages have just one numeric type, converting automatically between formats. This is:

• Slower, because of runtime conversions
• Potentially inaccurate, due to unexpected rounding

OCaml’s type system catches mismatches at compile time, guaranteeing that no type errors occur at runtime. Inside the computer all data are bits; the compiler uses types to generate correct machine code, and types are not stored during program execution.

Naive recursive power: npower

The function npower raises a float x to a non-negative integer power n:

let rec npower x n =
  if n = 0 then 1.0
  else x *. npower x (n - 1)
(* val npower : float -> int -> float = <fun> *)

The type reads: “pass in a float and an integer to return a float”. The rec keyword indicates the function is recursive — it calls itself.

Mathematical justification (for x != 0):

$x^0 = 1$ $x^{n+1} = x \times x^n$

For n >= 0, the computation terminates because the exponent decreases by 1 each time. For negative n, it would run forever:

$x^{-1} = x \times x^{-2} = x \times x \times x^{-3} = \dots$

Complexity: O(n) time (n multiplications) and O(n) space (not tail-recursive).

Efficient power: binary exponentiation

For large n, repeated multiplication is too slow. The square-and-multiply algorithm uses:

$x^1 = x$ $x^{2n} = (x^2)^n$ $x^{2n+1} = x \times (x^2)^n$

In OCaml:

let rec power x n =
  if n = 1 then x
  else if even n then
    power (x *. x) (n / 2)
  else
    x *. power (x *. x) (n / 2)
(* val power : float -> int -> float = <fun> *)

Example:

$2^{12} = 4^6 = 16^3 = 16 \times 256^1 = 16 \times 256 = 4096$

Only 4 multiplications instead of 12! Integer division / truncates, so (2n+1) / 2 = n.

Complexity: O(log n) time — at most 2 lg n multiplications, where lg n is log base 2. Space is also O(log n) because nesting occurs when the exponent is odd.

Comparison

For a 32-bit integer exponent, power makes at most 30 recursive calls (for 2^31 - 1). Making power tail-recursive by adding an accumulator is possible but the gain is minute for such small recursion depths.

The even test

The helper function uses modular arithmetic:

let even n = n mod 2 = 0
(* val even : int -> bool = <fun> *)

n mod 2 returns the remainder when dividing n by 2. If the remainder is 0, n is even.

Termination and exactness

The recurrence is bound to terminate because if n > 0, then n is smaller than both 2n and 2n+1. After enough recursive calls, the exponent reaches 1. The reasoning assumes exact arithmetic — floating-point is well-behaved here, but integer overflow occurs if values exceed the finite range of hardware integers.

Computation as reduction

Expression evaluation concerns expressions and the values they return. A computation proceeds by stepwise reduction:

$E_0 \rightarrow E_1 \rightarrow E_2 \rightarrow \dots \rightarrow v$

We write $E \rightarrow E'$ to say that $E$ reduces to $E'$. Mathematically, $E = E'$, but the computation goes from $E$ to $E'$ and never the other way.

A value is something that cannot be further reduced — a number like 42, a string like "hello", or a function like <fun>.

Functional vs imperative programming

Functional programming stays at the level of expressions. This may seem far removed from hardware, but for computing solutions to problems it is entirely adequate. Imperative programming requires a notion of states that can be observed and changed — assigning to variables, performing input/output — leading to conventional programs as coded in C.

Expressions vs values

An expression like 3 + 4 is not yet a value; it evaluates to 7. The expression nsum 3 evaluates through a sequence of reductions before yielding the value 6. The key distinction:

• Expressions may contain function calls, operators, and sub-expressions that need further evaluation
• Values are the end results: numbers, booleans, strings, functions, or constructed data

Stepwise reduction in OCaml

OCaml uses call-by-value evaluation: before applying a function, its argument is fully evaluated to a value. This means:

1. The argument expression is reduced to a value
2. The function body is then evaluated with the parameter bound to that value

This contrasts with call-by-name (evaluate the argument each time it is used) and call-by-need (evaluate at most once, caching the result). OCaml’s strict evaluation means recursive functions must have a base case that is reached without infinite descent.

Why expression evaluation matters

Modelling interaction and control (input/output, mutable state) requires additional concepts beyond pure expressions. But for the core of algorithm design — computing results from inputs — expression evaluation provides a clean, mathematically tractable foundation. The OCaml programmer thinks in terms of what an expression is (its value), not what it does (its effects).

Naive recursive summing: nsum

let rec nsum n =
  if n = 0 then 0
  else n + nsum (n - 1)
(* val nsum : int -> int = <fun> *)

The function computes $1 + 2 + \dots + n$ by recursion. A trace for nsum 3:

nsum 3 => 3 + (nsum 2)
       => 3 + (2 + (nsum 1))
       => 3 + (2 + (1 + (nsum 0)))
       => 3 + (2 + (1 + 0))
       => 6

The nesting of parentheses is not just notation — it indicates a real problem. The function gathers up numbers, but none of the additions can be performed until nsum 0 is reached. Meanwhile, the computer must store pending values on the call stack. For large n, say nsum 10000, the computation might fail due to stack overflow.

Iterative summing with accumulator: summing

let rec summing n total =
  if n = 0 then total
  else summing (n - 1) (n + total)
(* val summing : int -> int -> int = <fun> *)

The additional argument total is a running total (called an accumulator). If n is zero, it returns the accumulator; otherwise it adds n and continues. The trace:

summing 3 0 => summing 2 3
            => summing 1 5
            => summing 0 6
            => 6

The recursive calls do not nest — additions are done immediately as we go along. No stack of pending work builds up.

Comparison

The arithmetic progression formula

The sum can be computed in O(1) time using:

$1 + 2 + \dots + n = \frac{n(n+1)}{2}$

This is obviously the best approach if only the sum is needed. The recursive versions illustrate general patterns: naive recursion builds up deferred work, while accumulator-based iteration processes elements as it goes.

When nesting matters

The nesting in nsum is a specific instance of a general problem: if each recursive call must wait for the result of the next call, the intermediate values accumulate. Functions that avoid this are called iterative or tail-recursive.

Definition of tail recursion

A recursive function is tail-recursive (or iterative) if the recursive call is the last operation in the function — nothing remains to be done after it returns. The computation does not nest; each call’s work is completed before the next call begins.

(* Not tail-recursive: addition happens after the recursive call *)
let rec nsum n =
  if n = 0 then 0
  else n + nsum (n - 1)    (* + happens after nsum returns *)

(* Tail-recursive: nothing after the recursive call *)
let rec summing n total =
  if n = 0 then total
  else summing (n - 1) (n + total)   (* summing is the last thing *)

Tail-recursive functions produce computations resembling those done by while-loops in conventional languages.

Accumulators

An accumulator is an extra argument that carries a running result through recursive calls:

summing 3 0          (* start with accumulator = 0 *)
=> summing 2 3       (* accumulator updated to 3 *)
=> summing 1 5       (* accumulator updated to 5 *)
=> summing 0 6       (* accumulator updated to 6 *)
=> 6                 (* return final accumulator *)

The accumulator replaces the need to “remember” intermediate results on the call stack. Each recursive call updates it and passes it forward.

When to use accumulators (KISS)

The KISS principle (Keep It Simple, Stupid) applies:

• Write straightforward code first, avoiding only gross inefficiency
• Do not add accumulators merely out of habit
• If the program is too slow, profiling tools can pinpoint the cause

For power (binary exponentiation), adding an accumulator makes it iterative but complicates the code. The gain is minute — at most 30 nested calls for 32-bit exponents. Not worth it.

For nsum with n = 10000, the stack overflow risk is real. Worth it.

Recursion vs iteration trade-offs

Many algorithms are expressed naturally using recursion but only awkwardly using iteration. Dijkstra famously sneaked recursion into Algol-60 by inserting the words “any other occurrence of the procedure name denotes execution of the procedure” — carefully avoiding the word “recursion” to slip it past sceptical colleagues.

Tail recursion and the compiler

Tail-recursive code is only efficient if the compiler detects it and optimises accordingly (tail-call optimisation). OCaml performs this optimisation: a tail-recursive call reuses the same stack frame rather than allocating a new one. The main benefit is space (memory), though iterative code can sometimes also run faster.

Formal definition

$f(n) = O(g(n))$ means there exist constants $c$ and $n_0$ such that:

$|f(n)| \leq c \cdot |g(n)| \quad \text{for all } n \geq n_0$

In plain English: $|f(n)|$ is bounded above by some constant multiple of $|g(n)|$ for all sufficiently large n.

What Big O captures

The notation abstracts away details that do not affect asymptotic growth:

• Constant factors: $100n^2$ will beat $n^3$ in the long run. Constants depend on hardware, OS, and language — ignoring them makes comparisons broadly valid.
• Insignificant terms: If cost is $n^2 + 99n + 900$, the $n^2$ term eventually dominates. The $99n$ term is bigger for $n < 99$, but $n^2$ overtakes it.
• Small values of n: The role of $n_0$ in the definition is to ignore finitely many exceptions where the bound does not hold.

Simple facts

Constant factors and insignificant terms disappear:

$O(2g(n)) \text{ is the same as } O(g(n))$ $O(\log_{10} n) \text{ is the same as } O(\ln n)$ $O(n^2 + 50n + 36) \text{ is the same as } O(n^2)$

For the last one: $n^2 + 50n + 36 \leq 2n^2$ for $n \geq 51$, so we can double the constant factor and drop the lower-order terms.

Containment relationships

If $c$ and $d$ are constants with $0 < c < d$, then:

• $O(n^c) \subset O(n^d)$
• $O(c^n) \subset O(d^n)$
• $O(\log n) \subset O(n^c)$

The notation $O(f(n)) \subset O(g(n))$ means that if a function is $O(f(n))$, it is also $O(g(n))$ — the former gives a tighter bound. For example, if $f(n) = O(2^n)$ then trivially $f(n) = O(3^n)$, but the converse does not hold.

Why constant factors are ignored

• They seldom make a difference asymptotically: $100n^2$ beats $n^3$ for large n
• They are unstable: different hardware, operating system, or language changes them
• Ignoring them allows comparisons that remain valid across many circumstances

Limitations of Big O

Even ignoring constant factors, measurement units matter. Multiplication may be treated as one unit of cost, but multiplying two n-digit numbers for large n is itself expensive (relevant for cryptography). Few things are truly O(1): storing the number n requires O(log n) bits. An O(1) cost usually assumes operations fit within standard hardware arithmetic capacity.

Common complexity classes

Logarithms grow very slowly — O(log n) is excellent. Because O notation ignores constant factors, the base of the logarithm is irrelevant.

Growth rate table

How large an input can be processed in a given time:

The “gain” column shows what happens when going from 1 second to 1 minute. For exponential algorithms, the gain is a mere +6 — doubling hardware barely helps.

Exponential vs polynomial

• Polynomial complexity (O(nᶜ)): doubling the input increases cost by a constant factor. Practical for reasonable c, though c > 3 may still be problematic.
• Exponential complexity (O(2ⁿ)): can never handle large inputs, even with huge resources. Already with n = 20 the cost exceeds one million.

Faster hardware does not make good algorithms unnecessary. On the contrary, faster hardware magnifies the superiority of better algorithms: with sillySum (O(2ⁿ)), doubling processing power lets us go from n to n+1; with npower (O(n)), from n to 2n; with power (O(log n)), from n to n².

Simple recurrence relations

These recurrences are read directly from OCaml definitions. The constant work in the recursive step gets unit cost; the base case also gets unit cost. Since we only need an upper bound, these units represent the larger of the actual costs.

Summary of function complexities

Deriving recurrences from OCaml

Consider nsum:

let rec nsum n =
  if n = 0 then 0
  else n + nsum (n - 1)

Given n+1, it performs constant work (addition and subtraction) and calls itself with n. The recurrence:

$T(0) = 1$ $T(n+1) = T(n) + 1$

The closed form is $T(n) = n + 1$, giving O(n).

nsumsum: O(n²)

let rec nsumsum n =
  if n = 0 then 0
  else nsum n + nsumsum (n - 1)

The recurrence: $T(n+1) = T(n) + n$. Closed form:

$T(n) = (n-1) + \dots + 1 = \frac{n(n-1)}{2} = O(n^2)$

power: O(log n)

power divides n by 2 each step: $T(n) = T(n/2) + 1$. Since $T(2^n) = n+1$, we have $T(n) = O(\log n)$.

sillySum: O(2ⁿ)

let rec sillySum n =
  if n = 0 then 0
  else n + (sillySum (n-1) + sillySum (n-1)) / 2

Each recursive step makes two recursive calls. The function calls itself 2ⁿ times total. This is exponential — doubling hardware lets us go from n to n+1, which is practically useless.

The fix: use a let binding to compute a value once and reuse it:

let x = 2.0 in
let y = Float.pow x 20.0 in
y *. (x /. y)

Here y is computed once and used twice, avoiding the exponential blow-up.

Space vs time

• Space complexity can never exceed time complexity (it takes time to use space)
• Time complexity often greatly exceeds space complexity
• For example, sillySum is O(2ⁿ) time but only O(n) space (maximum call depth)
• Tail recursion reduces space, not time

List syntax

A list is an ordered series of elements; repetitions are significant. So [3; 5; 9] differs from [5; 3; 9] and from [3; 3; 5; 9]. Elements are separated with ; when constructing, as opposed to , syntax used for fixed-length tuples.

[3; 5; 9]                     (* int list *)
[(1, "one"); (2, "two")]      (* (int * string) list *)
[[3]; []; [5; 6]]             (* int list list *)

Type homogeneity

All elements of a list must have the same type. If $x_1, \dots, x_n$ all have type $\tau$, then [x1; ...; xn] has type $\tau$ list.

This contrasts with tuples, where (3, "hello") has type int * string and the elements may differ. The homogeneity property is checked at compile time, guaranteeing that no type errors occur at runtime when processing lists.

Lists of lists

Lists can contain lists as elements, forming nested structures:

let nested = [[1; 2]; [3]; []; [4; 5; 6]]
(* val nested : int list list *)

The empty list [] can appear as an element of a list-of-lists. Each inner list is independently sized.

concat (@) and List.rev

The infix operator @ (also called List.append) concatenates two lists:

[3; 5; 9] @ [2; 10]    (* [3; 5; 9; 2; 10] *)

List.rev reverses a list:

List.rev [(1, "one"); (2, "two")]    (* [(2, "two"); (1, "one")] *)

Two kinds of lists

There are exactly two kinds of list values:

Every list is either empty, or a head element attached to a tail list. This recursive definition is the foundation of all list processing — functions over lists follow the same two-case structure:

let rec f = function
  | [] -> ...        (* handle empty case *)
  | x :: xs -> ...   (* handle head x, recursive call on tail xs *)

The cons operator

The operator :: (pronounced “cons”, short for “construct”) puts a new element onto the head of an existing list:

1 :: [3; 5; 9]     (* [1; 3; 5; 9] *)
1 :: 2 :: []        (* [1; 2] *)

Critically, :: is an O(1) operation — it uses constant time and space regardless of the length of the list.

Internal structure

Lists are represented internally as a linked structure of cons cells. Each cons cell contains:

• A reference to the head (an element)
• A reference to the tail (another cons cell or [])

Adding a new element to a list merely hooks a new cons cell to the front of the existing structure. The existing structure continues to denote the same list as it did before — to see the new list, one must look at the new cons cell.

Sharing of tails

Because cons does not copy the tail, multiple lists can share their tails:

let xs = [3; 5; 9]
let ys = 1 :: xs     (* ys = [1; 3; 5; 9], xs still = [3; 5; 9] *)

ys and xs share the tail [3; 5; 9]. No copying occurred — only one new cons cell was allocated. This is a key efficiency property of functional lists: building a list with cons does not disturb existing lists.

The cons diagram

In the diagram notation:

:: --> :: --> :: --> :: --> []
 |      |      |      |
 1      3      5      9

Each :: is a cons cell. The rightward arrow points to the tail; the downward arrow points to the head. Taking the head or tail of a list is O(1) — each operation just follows one link.

The tail is not the last element; it is the list of all elements other than the head. The tail of [1; 3; 5; 9] is [3; 5; 9], and the tail of [9] is [].

Why this matters

Understanding the linked representation explains:

• Why cons is O(1): only one new cell allocated
• Why head/tail are O(1): following one pointer
• Why append is O(n): must copy the entire first list
• Why sharing is safe: OCaml values are immutable — no one can modify a shared tail

The null function

The function null tests whether a list is empty using pattern matching:

let null = function
  | [] -> true
  | x :: l -> false
(* val null : 'a list -> bool = <fun> *)

The two clauses match the two possible forms of a list: empty ([]) or non-empty (x :: l). The function returns true only for the empty list.

Head and tail access

hd returns the first element of a non-empty list; tl returns the list of remaining elements:

let hd (x :: l) = x
(* val hd : 'a list -> 'a = <fun> *)

let tl (x :: l) = l
(* val tl : 'a list -> 'a list = <fun> *)

Both functions raise a warning when compiled: the pattern matching is not exhaustive — the case [] is not handled. Applying hd or tl to [] raises an exception at runtime. The fix is to use null to check for emptiness beforehand, or better, to use proper two-case pattern matching.

Partial match warnings

OCaml’s compiler detects incomplete pattern matches. Two faulty declarations illustrate the problem:

(* Handles only empty lists -- non-empty case missing *)
let rec nlength [] = 0

(* Handles only non-empty lists -- empty case missing *)
let rec nlength (x :: xs) = 1 + nlength xs

These are two separate declarations. The second let replaces the first rather than extending it. To handle both cases, use the function keyword with | to separate clauses.

Polymorphic types

The primitive list functions have polymorphic types using type variables:

The symbols 'a and 'b are type variables (pronounced “alpha”, “beta”, etc.) and stand for any type. Code using these functions is checked for type correctness at compile time, and this guarantees that at run time, all elements of a list have the same type.

Pattern matching over hd and tl

Taking a list apart using combinations of hd and tl is hard to get right and seldom necessary. Pattern matching with the function keyword is the preferred approach:

let rec process = function
  | [] -> base_case
  | x :: xs -> ... x ... process xs ...

This is safer (no missing cases if both are covered) and clearer (the structure of the list is visible in the pattern).

Naive recursive length: nlength

let rec nlength = function
  | [] -> 0
  | x :: xs -> 1 + nlength xs
(* val nlength : 'a list -> int = <fun> *)

This is polymorphic and applies to all lists regardless of element type. A trace:

nlength [a; b; c] => 1 + nlength [b; c]
                  => 1 + (1 + nlength [c])
                  => 1 + (1 + (1 + nlength []))
                  => 1 + (1 + (1 + 0))
                  => 3

Like nsum, this function is not tail-recursive. The additions nest — 1 + (1 + (1 + 0)) — requiring O(n) space on the call stack.

Iterative length with accumulator: addlen

let rec addlen n = function
  | [] -> n
  | x :: xs -> addlen (n + 1) xs
(* val addlen : int -> 'a list -> int = <fun> *)

The function keyword introduces an extra (unnamed) argument that is pattern-matched. The integer accumulator n tracks the count so far:

addlen 0 [a; b; c] => addlen 1 [b; c]
                    => addlen 2 [c]
                    => addlen 3 []
                    => 3

The recursive calls do not nest — this is iterative and uses O(1) space.

Wrapper function

The efficient length function wraps addlen with an initial accumulator of zero:

let length xs = addlen 0 xs
(* val length : 'a list -> int = <fun> *)

Comparison

Both functions take O(n) time because you must examine each element to count it — there is no way around that. The accumulator improves space complexity only.

Why nlength is “naive”

The function nlength has the same flaw as nsum: it builds up deferred work (the 1 + expressions) that cannot be resolved until the base case is reached. For a list of length 10000, the call stack holds 10000 pending additions — a stack overflow waiting to happen. The iterative version addlen resolves the addition immediately (n + 1) and passes the result forward.

The append function

let rec append xs ys =
  match xs, ys with
  | [], ys -> ys
  | x :: xs, ys -> x :: append xs ys
(* val append : 'a list -> 'a list -> 'a list = <fun> *)

The pattern matches on a pair of lists. Two cases:

• If the first list is empty, return the second list unchanged
• Otherwise, cons the head of the first list onto the result of appending its tail to the second list

The infix operator @ is simply append:

let (@) = append

Evaluation trace

append [1; 2; 3] [4] => 1 :: append [2; 3] [4]
                      => 1 :: (2 :: append [3] [4])
                      => 1 :: (2 :: (3 :: append [] [4]))
                      => 1 :: (2 :: (3 :: [4]))
                      => [1; 2; 3; 4]

Complexity

Append scans its first argument and sets up a chain of cons operations:

• Time: O(n) where n is the length of the first argument
• Space: O(n) — each element of the first list is copied into a new cons cell
• Costs are independent of the second argument’s length

The string of pending cons operations means this function is not iterative. Adding an accumulator could make it iterative but would not improve the asymptotic complexity — concatenation inherently requires copying the first list. At best, an accumulator decreases the constant factor, but complicating the code is likely to increase it. Never add an accumulator merely out of habit.

Why the first list must be copied

Because OCaml lists are immutable, append cannot modify the last cons cell of the first list to point to the second list. Instead, it must copy every cons cell of the first list, with the final copy pointing to the second list. The second list is shared, not copied:

Original:  [1] --> [2] --> [3] --> []

Copy:      [1] --> [2] --> [3] --> [4] --> []
                                  ^
                                  | (shared)
Original:                  [4] --> []

Polymorphic type

Append’s type 'a list -> 'a list -> 'a list tells us two lists can be joined only if their element types agree. The result has the same element type.

Naive reverse: nrev — O(n²)

let rec nrev = function
  | [] -> []
  | x :: xs -> (nrev xs) @ [x]
(* val nrev : 'a list -> 'a list = <fun> *)

This reverses by recursively reversing the tail and appending the head as a singleton list at the end. A trace:

nrev [a; b; c] => (nrev [b; c]) @ [a]
               => ((nrev [c]) @ [b]) @ [a]
               => (((nrev []) @ [c]) @ [b]) @ [a]
               => (([] @ [c]) @ [b]) @ [a]
               => [c; b; a]

Why it is inefficient: each call to @ copies its first argument. For a list of length n:

• Reverse the tail (n-1 elements): n-1 conses in append
• Then cons x onto []: 1 cons
• Total for this step: n conses
• Reversing the tail requires n-1 more conses, and so forth

Total conses: $0 + 1 + 2 + \dots + n = \frac{n(n+1)}{2} = O(n^2)$

Space complexity is O(n) because the copies do not all exist at the same time.

Efficient reverse: rev_app — O(n)

let rec rev_app xs ys =
  match xs, ys with
  | [], ys -> ys
  | x :: xs, ys -> rev_app xs (x :: ys)
(* val rev_app : 'a list -> 'a list -> 'a list = <fun> *)

rev_app xs ys reverses the elements of xs and prepends them to ys. Trace:

rev_app [a; b; c] [] => rev_app [b; c] [a]
                      => rev_app [c] [b; a]
                      => rev_app [] [c; b; a]
                      => [c; b; a]

This performs exactly n conses for an n-element list — one per element as it moves from the input to the accumulator. Time is O(n), space is O(1) (tail-recursive).

The wrapper hides the accumulator:

let rev xs = rev_app xs []
(* val rev : 'a list -> 'a list = <fun> *)

Reduction in strength

The key improvement comes from replacing an expensive operation (@, which is O(n)) with a series of cheap operations (::, which is O(1)). This technique is called reduction in strength and is a common pattern in algorithm design. It originated when hardware lacked multiply instructions — repeated addition was cheaper than multiplication.

Why consing to an accumulator reverses

Cons adds to the front of a list, so as elements are consed to the accumulator in order, the accumulator builds up in reverse:

If the reverse order in the accumulator is undesirable, an extra call to rev at the end fixes it — but that doubles the cost. Sometimes the iterative function can be slower than the recursive one if an extra reversal is needed.

Splitting a list

take and drop divide a list into two parts at a given index i. Given a list xs = [x₀, ..., xᵢ₋₁, xᵢ, ..., xₙ₋₁], take i xs returns the first i elements while drop i xs returns everything from position i onwards.

Both functions share the same type signature:

int -> 'a list -> 'a list

take

take copies the first i elements into a new list. It is not tail-recursive, but making it iterative would not improve its efficiency: copying i elements inherently requires O(i) time and space.

let rec take i = function
  | [] -> []
  | x::xs ->
      if i > 0 then x :: take (i - 1) xs
      else []

drop

drop simply skips over the first i elements. It is tail-recursive and uses only O(1) space.

let rec drop i = function
  | [] -> []
  | x::xs ->
      if i > 0 then drop (i-1) xs
      else x::xs

Although both are O(i) in time, drop is much faster than take in practice because skipping elements is cheaper than copying them: drop has a smaller constant factor.

Applications

take and drop are used throughout the course for divide-and-conquer algorithms. A common pattern: divide a list into two roughly equal halves for recursive processing, as seen in mergesort where the input is split at the midpoint using take and drop.

The simplest search

Linear search finds a target value in a collection by comparing it against each element in turn. If the target appears in the list, it is found in n/2 steps on average; the worst case requires checking all n elements.

Performance

Linear search is the most general: it needs only the ability to test equality between keys. Ordered search and indexed lookup are exponentially faster but impose additional constraints on the data.

When to use linear search

• Small collections: the constant factors are low and the code is simple.
• Unordered data: when sorting or indexing would be more expensive than the search itself.
• Prototyping: it is the natural starting point before optimising with better algorithms.

For large, frequently searched datasets, linear search is rarely acceptable. Consider that a web search engine scanning billions of pages linearly would be impossibly slow; it is only through indexing that sub-second queries are possible. Nevertheless, linear search remains the conceptual foundation on which more sophisticated search algorithms are built.

Polymorphic equality

OCaml provides polymorphic equality operators that work across many types without requiring explicit type-specific comparison functions:

These operators inspect the structure of values and apply a consistent ordering.

The member function

member uses linear search with polymorphic equality to test whether a value appears in a list:

let rec member x = function
  | [] -> false
  | y::l ->
     if x = y then true
     else member x l

Its type, 'a -> 'a list -> bool, reflects that it works for any type that supports polymorphic equality.

Which types support it?

Limitations and controversy

Polymorphic equality cannot compare function values: two functions that compute the same result from identical source code may be stored at different memory addresses, and OCaml has no principled way to test functional equivalence.

The presence of polymorphic equality is contentious in the OCaml community. For small programs and learning, it is convenient and safe enough. In large systems, however, its use can mask bugs: it may compare values that should not be compared, or impose structural ordering where none is meaningful. Many large-scale OCaml codebases avoid it in critical paths, preferring explicit comparison functions passed as arguments. For the purposes of this course, polymorphic equality is sufficient.

zip

zip pairs up corresponding elements from two lists into a single list of pairs. If the lists differ in length, surplus elements from the longer list are silently discarded.

let rec zip xs ys =
  match xs, ys with
  | (x::xs, y::ys) -> (x, y) :: zip xs ys
  | _ -> []

Type: 'a list -> 'b list -> ('a * 'b) list

Key points:

• The wildcard pattern _ matches anything and signals that the second clause discards its arguments. Using _ is clearer than a named variable when the value is not used.
• Pattern order matters: the first clause (x::xs, y::ys) is tried before the wildcard. Only when at least one list is empty does the second clause fire. If the clauses were reversed, zip would always return [].

unzip

unzip reverses the operation, taking a list of pairs and returning a pair of lists:

let rec unzip = function
  | [] -> ([], [])
  | (x, y)::pairs ->
      let xs, ys = unzip pairs in
      (x::xs, y::ys)

Type: ('a * 'b) list -> 'a list * 'b list

The local let binding let xs, ys = unzip pairs in ... destructures the result of the recursive call. In general, let P = E₁ in E₂ matches pattern P against the value of expression E₁ and binds the variables in P within E₂.

conspair helper

An alternative version of unzip extracts the destructuring into a helper function:

let conspair ((x, y), (xs, ys)) = (x::xs, y::ys)

let rec unzip = function
  | [] -> ([], [])
  | xy :: pairs -> conspair (xy, unzip pairs)

conspair takes a pair ((x, y), (xs, ys)) and returns (x::xs, y::ys). While not every local binding can be eliminated this cleanly, the pattern of factoring out helper functions is a useful technique for keeping code readable.

Problem statement

Given a till with unlimited supplies of coins in certain denominations (listed in descending order), find a combination of coins that sums to a target amount. The goal is to minimise the number of coins.

Greedy approach

The algorithm always tries the largest coin first: if the largest coin does not exceed the remaining amount, use it and recurse on the reduced amount. Otherwise, discard that coin denomination and try the next largest.

let rec change till amt =
  match till, amt with
  | _, 0         -> []
  | [], _        -> raise (Failure "no more coins!")
  | c::till, amt -> if amt < c then change till amt
                    else c :: change (c::till) (amt - c)

Key design decisions

• Base case of zero, not one: when amt = 0, the result is [] (no coins needed). Using zero as the base case is simpler than using one; most iterative procedures are cleanest when they do nothing in the base case. A base case of one is often a sign of a novice programmer.
• The coin is not removed from the till after use: the recursive call uses c::till (not till), since we have unlimited supply of each coin.
• Failure via exceptions: if the till becomes empty while the amount is still nonzero, the function raises Failure.

Greedy failure

The greedy algorithm is not always correct. Example: making 6 using coins [5, 2].

Yet 6 = 2 + 2 + 2 is a valid solution. The greedy algorithm fails because it commits to the 5 coin and cannot backtrack. Greedy algorithms work for certain coin systems (e.g., UK coins: 1, 2, 5, 10, 20, 50) but not in general.

Returning all solutions

Instead of returning a single solution (or failing), we can return all possible ways of making change. The result type becomes int list list (a list of solutions, each solution a list of coins).

Base version

let rec change till amt =
  match till, amt with
  | _       , 0   -> [ [] ]
  | []      , _   -> []
  | c::till , amt -> if amt < c then change till amt
                     else let rec allc = function
                             | [] -> []
                             | cs :: css -> (c::cs) :: allc css
                          in
                             allc (change (c::till) (amt - c)) @
                                   change till amt

Key differences from the greedy version:

• Success base case: [[]] (a list containing the empty solution), not just []. This represents “there is one way: use no coins”.
• Failure base case: [] (empty list of solutions), rather than raising an exception.
• Two sources of solutions: either use the current coin (change (c::till) (amt - c)) or skip it (change till amt). The locally declared allc function prepends the current coin c to each solution from the first source, and the results are concatenated with @.

Stepwise refinement: faster version

The base version uses many :: and @ operations. A refined version introduces accumulating parameters to eliminate them:

let rec change till amt chg chgs =
  match till, amt with
  | _       , 0   -> chg::chgs
  | []      , _   -> chgs
  | c::till , amt -> if amt < 0 then chgs
                     else change (c::till) (amt - c) (c::chg)
                                 (change till amt chg chgs)

This version runs several times faster than the base version. The technique of starting with a simple program and incrementally improving it is called stepwise refinement.

Exponential blow-up

Even the refined version cannot escape the fundamental problem: the number of solutions grows rapidly. Using UK coins (50, 20, 10, 5, 2, 1), there are 4,366 ways to make change for 99. No algorithm can list all solutions faster than the number of solutions, so the runtime remains exponential in the amount.

Why sort?

Sorting is one of the most deeply studied topics in algorithm design. Common applications:

Information-theoretic lower bound

How many comparisons are needed to sort n items? Consider the decision tree model:

• There are n! possible permutations of n distinct elements.
• Each comparison eliminates roughly half of the remaining possibilities.
• With C(n) comparisons, we can distinguish at most 2^{C(n)} outcomes.

For the algorithm to be correct for all inputs, we must have:

Taking logarithms:

This is the information-theoretic lower bound: any comparison-based sorting algorithm must perform at least O(n log n) comparisons in the worst case. Mergesort achieves this bound exactly, making it asymptotically optimal.

Beyond comparisons

The lower bound applies only to comparison-based sorting. Non-comparison sorts (e.g., radix sort) can achieve O(n) time for certain restricted inputs, such as integers within a fixed range. This does not contradict the lower bound because such algorithms exploit properties of the data beyond pairwise comparisons.

How it works

Insertion sort builds the sorted output one element at a time by inserting each input element into its correct position among the already-sorted elements.

ins inserts a single element into a sorted list:

let rec ins x = function
  | [] -> [x]
  | y::ys -> if x <= y then x :: y :: ys
             else y :: ins x ys

On average, ins performs n/2 comparisons to insert into a list of length n.

insort applies ins to each element of the input:

let rec insort = function
  | [] -> []
  | x::xs -> ins x (insort xs)

Complexity

The quadratic runtime makes insertion sort nearly useless for large inputs. On the DECstation benchmarks referenced in the course, insertion sort took 174 seconds to sort 10,000 random numbers, while quicksort took 0.74 seconds: over 200 times slower.

Why study it?

Insertion sort is easy to code and illustrates fundamental concepts:

• It is the natural first attempt at a sorting algorithm.
• Mergesort and heapsort can be understood as refinements of insertion sort.
• For very small lists (length < 5 or so), insertion sort’s low constant factors can make it the fastest choice, and production quicksort implementations often switch to insertion sort for small partitions.

The bottleneck is the number of comparisons (O(_n_²)), not the absence of tail recursion. Making insertion sort iterative would not change its asymptotic complexity.

Divide, conquer, combine

Quicksort (invented by Sir Tony Hoare) follows the divide-and-conquer paradigm:

1. Choose a pivot element a from the input.
2. Divide: partition the remaining elements into those ≤ a and those > a.
3. Conquer: recursively sort each partition.
4. Combine: append the sorted left partition to the pivot followed by the sorted right partition.

List-based implementation

let rec quick = function
  | [] -> []
  | [x] -> [x]
  | a::bs ->
       let rec part l r = function
         | [] -> (quick l) @ (a :: quick r)
         | x::xs ->
             if (x <= a) then
               part (x::l) r xs
             else
               part l (x::r) xs
        in
        part [] [] bs

Three clauses:

• Empty list: already sorted.
• Singleton list [x]: already sorted (this special case avoids unnecessary work).
• Two or more elements: use the head a as pivot, partition the tail bs.

The locally declared part function accumulates elements ≤ pivot in l and elements > pivot in r.

Complexity analysis

Average case: with random data, the pivot typically divides the input into roughly equal halves. On the course benchmarks, quicksort sorts 10,000 random numbers in ~0.74 seconds.

Worst case: when the input is already sorted or reverse-sorted, nearly all elements fall into one partition. The work is not divided evenly, and complexity degenerates to quadratic. Randomising the input (or choosing a random pivot) makes the worst case highly unlikely in practice.

Eliminating append

The standard quicksort uses @ to combine sorted partitions in the combine phase. This can be eliminated using an accumulating parameter sorted, following the same technique used to remove @ from list reversal.

let rec quik = function
  | ([], sorted) -> sorted
  | ([x], sorted) -> x::sorted
  | a::bs, sorted ->
     let rec part = function
       | l, r, [] -> quik (l, a :: quik (r, sorted))
       | l, r, x::xs ->
           if x <= a then
             part (x::l, r, xs)
           else
             part (l, x::r, xs)
     in
     part ([], [], bs)

How it works

Calling quik(xs, sorted) reverses the elements of xs and prepends them to sorted. The evaluation order inside part is significant:

1. quik (r, sorted) is performed first (sort the right partition and prepend to sorted).
2. The pivot a is consed onto that result.
3. quik (l, ...) sorts the left partition and prepends it.

The sorted parameter accumulates the result, replacing the repeated concatenation (quick l) @ (a :: quick r).

Speed comparison

The append-free version is significantly faster. An imperative Pascal quicksort (using in-place array swaps, from Sedgewick) is only slightly faster than quik. This near-agreement is surprising given that linked lists have more overhead than arrays. In realistic applications, comparisons dominate the runtime, and list overhead matters less than one might expect.

On the DECstation benchmarks, append-free quicksort sorts 10,000 random numbers in approximately 0.53 seconds, compared to 0.74 seconds for the append-based version.

merge

merge combines two already sorted lists into a single sorted list. It generalises insertion to two lists:

let rec merge = function
  | [], ys -> ys
  | xs, [] -> xs
  | x::xs, y::ys ->
      if x <= y then
        x :: merge (xs, y::ys)
      else
        y :: merge (x::xs, ys)

At each step, merge compares the heads of both lists and takes the smaller. It does at most m + n − 1 comparisons, where m and n are the lengths of the input lists. If n = 1, merging degenerates to insertion: it does proportionally more work for less gain.

merge is not tail-recursive, but making it iterative would offer little benefit for the same reasons that apply to append.

Top-down mergesort

Mergesort divides the input into two equal halves (unlike quicksort, which divides by value), sorts each half recursively, and merges the sorted halves:

let rec tmergesort = function
  | [] -> []
  | [x] -> [x]
  | xs ->
      let k = List.length xs / 2 in
      let l = tmergesort (take k xs) in
      let r = tmergesort (drop k xs) in
      merge (l, r)

Complexity

Because take and drop divide the input into equal parts (differing by at most one element), the recurrence is always T(n) = 2_T_(n/2) + n, giving guaranteed O(n log n) in the worst case. Mergesort is asymptotically optimal.

Comparison with quicksort

Mergesort is safe (no quadratic worst case) but typically slower than quicksort on random data. The choice of algorithm depends on the application: if worst-case behaviour matters (e.g., real-time systems or adversarial inputs), mergesort is preferable. If average-case performance is the priority and inputs are not expected to be pathologically ordered, quicksort is the better choice.

Declaring a new type

OCaml’s type declaration introduces new types beyond the built-in ones. An enumeration type is a type defined by listing its possible values (called constructors):

type vehicle = Bike | Motorbike | Car | Lorry

This declaration:

• Creates a new type called vehicle.
• Creates four new constants (Bike, Motorbike, Car, Lorry) of that type.
• The constructors serve both as values and as patterns for pattern matching.

Pattern matching on constructors

Once declared, the new type behaves like a built-in type:

let wheels = function
  | Bike -> 2
  | Motorbike -> 2
  | Car -> 4
  | Lorry -> 18

The type of wheels is vehicle -> int. The compiler checks that all cases are covered and warns about missing or redundant patterns.

Why not use integers or strings?

The compiler chooses the internal integer representation automatically. Type safety prevents confusion between different enumeration types: Bike and Red (from a colour type) are distinct and cannot be accidentally interchanged.

Most programming languages support enumeration types. Common examples include days of the week, colours, and states in a state machine.

Carrying data

OCaml generalises enumeration types by allowing constructors to carry data:

type vehicle = Bike
             | Motorbike of int   (* engine size in CCs *)
             | Car       of bool  (* true if a Reliant Robin *)
             | Lorry     of int   (* number of wheels *)

• Bike is a constant constructor: it is a value by itself.
• Motorbike 450 is a vehicle constructed from the integer 450.
• Car true and Car false are distinct vehicles from the same constructor.
• Motorbike of int and Lorry of int are distinct types: even though both carry an int, OCaml tracks which constructor was used. Motorbike 450 is never confused with Lorry 450.

Pattern matching with arguments

Constructors carrying data can be destructured in patterns:

let wheels = function
  | Bike -> 2
  | Motorbike _ -> 2           (* discard the engine size *)
  | Car robin -> if robin then 3 else 4  (* bind to robin *)
  | Lorry w -> w               (* extract the wheel count *)

Pattern elements:

• Named variable (robin, w): binds the carried value for use in the right-hand side.
• Wildcard _: matches any carried value and discards it. The underscore signals that the argument is irrelevant to the computation.

Mixed-type-like lists

Datatypes with constructors carrying different payload types allow heterogeneous collections:

[Bike; Car true; Motorbike 450]

This is a vehicle list. It behaves almost like a mixed-type list containing integers and booleans. The datatype mechanism reduces the impact of the restriction that all list elements must share the same type.

Nested patterns

Patterns can be as complex as needed and may combine constructors from multiple datatypes. For example, patterns can deconstruct lists and vehicles simultaneously, or match integer and string constants inside constructors. OCaml compiles pattern matching efficiently.

Exception declarations

Exceptions are declared like constructors of a special built-in type exn:

exception Failure
exception NoChange of int

• Failure is a simple exception carrying no data.
• NoChange 6 carries an integer explaining which amount could not be changed.

Each exception declaration introduces a distinct sort of error that can be caught separately.

Raising and handling

• raise abandons the current computation and propagates the exception upward.
• try ... with catches exceptions and attempts an alternative computation.

try
  print_endline "pre exception";
  raise (NoChange 1);
  print_endline "post exception";
with
  | NoChange _ -> print_endline "handled a NoChange exception"

The output is pre exception followed by handled a NoChange exception. The code after raise is never reached. The handler matches exceptions using pattern matching, and only the most recently entered handler that matches is invoked.

Dynamic matching

Exception handlers are resolved dynamically (at runtime). This contrasts with how OCaml resolves variable bindings, which happens statically (at compile time). A function can raise an exception deep in a call chain, and the handler might be in a completely different part of the program.

Comparison with Java

OCaml’s exceptions have no checked exception mechanism: nothing in a function’s type indicates which exceptions it might raise. In Java, checked exceptions must be declared in the method signature. This is a trade-off: OCaml gives more flexibility at the cost of less static documentation of failure modes.

The option type

An alternative to exceptions is the option type:

type 'a option = None | Some of 'a

The option type makes failure explicit in the type: a function returning 'a option clearly signals that it may fail. The drawback is that every caller must check for None, which can clutter the code.

When to use each

• Exceptions: when failure is truly exceptional and the normal control flow should not be littered with error checks.
• Option: when failure is a routine outcome that callers should handle explicitly.

The problem with greed

The greedy change algorithm fails when the largest-coin-first strategy leads to a dead end (e.g., making 6 from [5, 2]). We need a way to undo a coin choice and try alternatives: this is backtracking.

Exception-driven backtracking

The idea is elegant: enclose each recursive call in an exception handler. If the recursive call fails (raises Change), the handler catches it and tries the next alternative.

exception Change

let rec change till amt =
  match till, amt with
  | _, 0         -> []
  | [], _        -> raise Change
  | c::till, amt -> if amt < 0 then raise Change
                    else try c :: change (c::till) (amt - c)
                         with Change -> change till amt

How it works

• If amt = 0: success, return [].
• If the till is empty or amt goes negative: dead end, raise Change.
• Otherwise: try using the largest coin. If the recursive call raises Change, catch it and try the next coin instead.

The exception handler always undoes the most recent choice. If all alternatives fail, Change propagates to the previous handler, and so on. If change is truly impossible, Change reaches the top level uncaught.

Trace: change [5; 2] 6

change [5; 2] 6
→ try 5::change [5; 2] 1
→ try 5::(try 5::change [5; 2] (-4)    ← amt < 0, raise Change
           with Change → change [2] 1)
→ try 5::(try 2::change [2] (-1)       ← amt < 0, raise Change
           with Change → change [] 1)   ← empty till, raise Change
→ change [2] 6                          ← handler caught it, try [2]
→ try 2::change [2] 4
→ try 2::(try 2::change [2] 2
→ try 2::(try 2::(try 2::change [2] 0  ← amt = 0, success: []
           with Change → change [] 2)
→ [2; 2; 2]                             ← success!

Observe how handlers nest as the recursion deepens, and drop away once a branch succeeds.

Comparison with list-of-all-solutions

Backtracking is dramatically more space-efficient and faster when only one solution is needed, since it stops searching upon success and does not accumulate partial results.

Recursive datatype definition

A binary tree is a recursive datatype where each node is either empty or holds a label and two subtrees:

type 'a tree =
  Lf
| Br of 'a * 'a tree * 'a tree

• Lf (leaf) represents an empty tree.
• Br(v, t1, t2) is a branch node with label v, left subtree t1, and right subtree t2.
• The type parameter 'a makes it polymorphic: an int tree stores integers, a string tree stores strings, etc.

Constructing a tree

Br(1, Br(2, Br(4, Lf, Lf),
             Br(5, Lf, Lf)),
       Br(3, Lf, Lf))

This builds a tree with root label 1, left child 2 (with children 4 and 5), and right child 3. All leaves are Lf.

Lists as a recursive datatype

Built-in OCaml lists could be declared as a user-defined type:

type 'a mylist =
  Nil
| Cons of 'a * 'a mylist

This mirrors the built-in [] and :: exactly. The only thing not reproducible is the [a; b; c] syntactic sugar, which is part of the OCaml grammar.

Other recursive datatypes

Not all datatypes need to be both recursive and polymorphic:

A shape value represents the structure of a binary tree with no data attached. The option type is polymorphic (useful for any type) but not recursive (it does not contain further options).

Basic measures

Three functions characterise the size and shape of a binary tree:

count — the number of branch (Br) nodes:

let rec count = function
  | Lf -> 0
  | Br (v, t1, t2) -> 1 + count t1 + count t2

depth — the length of the longest path from root to a leaf:

let rec depth = function
  | Lf -> 0
  | Br (v, t1, t2) -> 1 + max (depth t1) (depth t2)

leaves — the number of leaf (Lf) nodes:

let rec leaves = function
  | Lf -> 1
  | Br (v, t1, t2) -> leaves t1 + leaves t2

Fundamental invariants

These measures are related by two properties, provable by structural induction:

The second invariant gives a striking practical fact: a tree of depth 20 can store up to 2²⁰ − 1 ≈ one million elements. Access paths to any element are at most 20 steps long, compared with up to one million steps in a linear list.

ftree: building labelled complete trees

let rec ftree k n =
  if n = 0 then Lf
  else Br (k, ftree (2 * k) (n - 1), ftree (2 * k + 1) (n - 1))

ftree k n builds a complete binary tree of depth n where nodes are labelled according to the standard array-to-tree mapping: the root gets label k, the left child gets 2_k_, and the right child gets 2_k_ + 1. This labelling scheme is the foundation for functional arrays (Braun trees), which are covered in the following lecture.

Dictionary operations

A dictionary (or map) associates keys with values. The core operations are:

An abstract type would hide the internal representation behind these operations. This course does not cover OCaml’s module system, so operations are declared individually.

Association list

The simplest representation is an association list: a list of (key, value) pairs.

lookup

Linear search through the list:

exception Missing

let rec lookup a = function
  | [] -> raise Missing
  | (x, y) :: pairs ->
      if a = x then y
      else lookup a pairs

O(n) time, where n is the number of entries.

update

Simply cons the new pair onto the front:

let update (l, b, y) = (b, y) :: l

O(1) time, which is optimal.

Limitations

The space problem is significant: obsolete entries accumulate and are never removed. Deleting an entry would require finding it first, which would increase update from O(1) to O(n). Association lists are acceptable only when there are few keys in use, or when fast updates matter more than fast lookups.

The BST invariant

A binary search tree (BST) is a binary tree where each branch node holds a (key, value) pair, and the keys satisfy:

• All keys in the left subtree are less than the node’s key.
• All keys in the right subtree are greater than the node’s key.
• This property holds recursively at every node.

BSTs require a total ordering on keys (e.g., numeric or lexicographic order). This is a stronger requirement than association lists, which need only equality.

Balanced vs. unbalanced

Building a BST by repeatedly inserting elements in increasing or decreasing order produces a degenerate tree that is essentially a linked list. This is analogous to quicksort’s worst case: the pivot (root key) does not divide the data evenly.

Treesort

If we insert all elements into a BST and then perform an inorder traversal, the result is a sorted list. This algorithm is called treesort. Its complexity mirrors that of quicksort: O(n log n) average case, O(_n_²) worst case.

Self-balancing trees

Self-balancing trees (e.g., Red-Black trees, AVL trees) maintain the O(log n) guarantee in the worst case by automatically restructuring the tree after insertions and deletions. They are more complex to implement but are the standard choice for production dictionary data structures. The course mentions them but does not cover their implementation.

lookup

lookup navigates the tree by comparing the sought key against each node’s key:

exception Missing of string

let rec lookup b = function
  | Br ((a, x), t1, t2) ->
      if b < a then
        lookup b t1
      else if a < b then
        lookup b t2
      else
        x
  | Lf -> raise (Missing b)

Three cases at each branch:

• Smaller: search left subtree.
• Greater: search right subtree.
• Equal: return the stored value.
• Leaf reached: the key is not present; raise Missing.

In a balanced tree, lookup is O(log n). The exception is parameterised with the missing key so the caller knows what was sought.

update

update follows the same search path but reconstructs the tree along the way:

let rec update k v = function
  | Lf -> Br ((k, v), Lf, Lf)
  | Br ((a, x), t1, t2) ->
      if k < a then
        Br ((a, x), update k v t1, t2)
      else if a < k then
        Br ((a, x), t1, update k v t2)
      else (* a = k *)
        Br ((a, v), t1, t2)

Functional update: path copying

The key insight is that update does not modify the existing tree in place. Instead, it creates a new tree that shares unchanged subtrees with the original:

Only the nodes on the path from the root to the updated node are copied. Unchanged subtrees are shared between the old and new trees. For a balanced tree, this means O(log n) time and O(log n) extra space per update. This is a classic example of persistent (or purely functional) data structures: old versions remain valid and accessible after updates.

Three depth-first orders

Tree traversal means visiting every node in a systematic order. Knuth identifies three depth-first traversals, all of which process the left subtree before the right subtree. They differ only in when the node’s label is visited:

Naive implementations

Each traversal converts a tree into a list of labels:

let rec preorder = function
  | Lf -> []
  | Br (v, t1, t2) ->
      [v] @ preorder t1 @ preorder t2

let rec inorder = function
  | Lf -> []
  | Br (v, t1, t2) ->
      inorder t1 @ [v] @ inorder t2

let rec postorder = function
  | Lf -> []
  | Br (v, t1, t2) ->
      postorder t1 @ postorder t2 @ [v]

Example: given a tree with root A, left child B (children D, E), right child C (children F, G):

Inorder on BSTs

Applying inorder to a binary search tree yields the keys in sorted order. This property is the basis of treesort: build a BST from the input, then traverse inorder to get the sorted list.

Inefficiency

All three naive traversals suffer from the same problem: repeated uses of @ (append). In the worst case (a degenerate tree), the time complexity is O(_n_²) because each @ copies its first argument. The next note shows how to fix this with accumulating parameters.

The problem with append

The naive traversal functions use @ in recursive calls. In a degenerate (unbalanced) tree, this leads to O(_n_²) total time because each append copies the left result. The fix follows the same pattern used throughout the course: introduce an accumulating parameter to eliminate @.

Efficient versions

Each function takes a pair (tree, accumulator), where the accumulator vs collects the result:

let rec preord = function
  | Lf, vs -> vs
  | Br (v, t1, t2), vs ->
      v :: preord (t1, preord (t2, vs))

let rec inord = function
  | Lf, vs -> vs
  | Br (v, t1, t2), vs ->
      inord (t1, v::inord (t2, vs))

let rec postord = function
  | Lf, vs -> vs
  | Br (v, t1, t2), vs ->
      postord (t1, postord (t2, v::vs))

All three are O(n) in time for a tree of size n. They use cons (::) instead of append (@), a classic example of reduction in strength: replacing an expensive operation with a series of cheap ones.

Relating efficient and naive versions

The efficient versions satisfy equations that connect them to the naive ones. For example:

inord(t, vs) = inorder(t) @ vs

This identity means that inord computes the same result as the naive inorder followed by append, but does so in linear time rather than quadratic.

All three are depth-first

Preorder, inorder, and postorder are all depth-first traversals: each traverses the entire left subtree before touching the right subtree. An alternative is breadth-first traversal, which visits nodes level by level, covered in the Queues lecture.

Conventional vs. functional arrays

Functional arrays are a finite map from integers to data, where every update produces a new array rather than mutating the existing one. The challenge is doing this efficiently without copying the entire array.

Braun trees

The representation, credited to W. Braun, stores array elements in a balanced binary tree where the path to element i is determined by the binary representation of i:

The subscript arithmetic:

if k = 1        → the root
if k mod 2 = 0  → go left, then recurse on k/2
if k mod 2 = 1  → go right, then recurse on k/2

Equivalently: write k in binary, discard the leading 1, reverse the remaining bits, and interpret 0 as “go left” and 1 as “go right”. This scheme guarantees a balanced tree, ensuring O(log n) access for all subscripts.

sub: array lookup

exception Subscript

let rec sub = function
  | Lf, _ -> raise Subscript
  | Br (v, t1, t2), k ->
      if k = 1 then v
      else if k mod 2 = 0 then
        sub (t1, k / 2)
      else
        sub (t2, k / 2)

Divides the subscript by 2 repeatedly until reaching 1. At each step, the parity determines which subtree to follow. If a leaf is reached before subscript 1, the position does not exist and Subscript is raised.

update: functional array update

let rec update = function
  | Lf, k, w ->
      if k = 1 then
        Br (w, Lf, Lf)        (* extend the array *)
      else
        raise Subscript        (* gap in the tree *)
  | Br (v, t1, t2), k, w ->
      if k = 1 then
        Br (w, t1, t2)         (* replace root value *)
      else if k mod 2 = 0 then
        Br (v, update (t1, k / 2, w), t2)
      else
        Br (v, t1, update (t2, k / 2, w))

Two cases for k = 1:

• At a leaf: extend the array by creating a new branch (the array grows).
• At a branch: replace the existing value (update in place functionally).

Like BST update, only the path from root to the target index is copied, giving O(log n) time and space. Unchanged subtrees are shared.

Why binary?

The subscript arithmetic works because binary decisions (left/right) reduce the search space by half at each step. This is the fundamental reason binary is important in computer science: an if-then-else leads to binary branching, which turns an O(n) cost into O(log n). Two is the smallest integer divisor that achieves this reduction.

Functions as first-class values

In OCaml, functions can be:

• passed as arguments to other functions
• returned as results from other functions
• put into data structures like lists, trees, and tuples
• but not tested for equality (comparing function addresses would test identity, not equivalence)

[(fun n -> n * 2); (fun n -> n * 3); (fun n -> n + 1)]
(* : (int -> int) list = [<fun>; <fun>; <fun>] *)

This is a list of three functions, each of type int -> int. Storing computational behaviour in data structures is a powerful abstraction that reaches its full realisation in object-oriented programming.

Higher-order functions (functionals)

A functional or higher-order function is a function that operates on other functions - either by taking them as arguments or returning them as results. The name comes from mathematics: the differential operator maps functions to their derivatives.

Why functions as values matter

Progress in programming languages can be measured by what abstractions they admit. Conditional expressions replaced numeric-sign-based jumps. Parametric types like 'a list gave us type-safe generics. Functions-as-values is the next step: it captures common program structures once and for all.

• Avoids writing repetitive recursive functions for similar patterns
• Lets you define ad-hoc operations inline without naming them
• Enables libraries of combinators (map, filter, fold, etc.) that generalise across many domains
• Is the foundation of Church’s λ-calculus, which is equivalent in power to Turing machines and is the direct precursor of fun-notation

Key limitations

• Functions cannot be tested for equality in OCaml. Two separately compiled functions that compute identical results are not considered equal; the comparison would reduce to comparing machine addresses, which is a low-level detail with no place in a principled language.
• Functional arguments and results must have consistent types enforced by the type checker at compile time.

fun-notation

The fun-notation expresses a non-recursive function value without giving the function a name:

fun n -> n * 2
(* : int -> int = <fun> *)

This is the function f such that f(n) = n × 2. It can be applied immediately:

(fun n -> n * 2) 17
(* : int = 34 *)

The expression fun n -> n * 2 has the same value as a named declaration:

let double n = n * 2
(* val double : int -> int = <fun> *)

These two forms are equivalent. The fun form is used when the function is needed only once or is being passed as an argument to another function.

Pattern-matching anonymous functions

There are three equivalent ways to define an is_zero function:

The function keyword is shorthand for fun x -> match x with .... It introduces an anonymous argument that is immediately pattern-matched against the clauses that follow. This is convenient for functions defined by pattern-matching on a single argument.

When to use each form

• Use fun x -> E when you need a simple unnamed function taking one argument.
• Use function P1 -> E1 | P2 -> E2 when the anonymous function pattern-matches on its single argument.
• Use let f x = E when you want to give the function a name for reuse.
• Use let rec when the function needs to call itself recursively (anonymous functions via fun cannot be recursive).

What is currying?

Currying is the technique of expressing a function taking multiple arguments as nested functions, each taking a single argument. A curried function returns another function as its result.

Consider the string concatenation operator (^):

(^)
(* : string -> string -> string = <fun> *)

The type string -> string -> string means “a function that takes a string and returns a function from string to string”. Compare with an uncurried version using pairs:

Defining curried functions

A curried function uses nested fun-notation:

let prefix = fun a -> fun b -> a ^ b
(* val prefix : string -> string -> string = <fun> *)

Applying this function to one argument yields another function:

let promote = prefix "Senior "
(* val promote : string -> string = <fun> *)

promote "Professor"
(* : string = "Senior Professor" *)

Promotion via partial application

Supplying the first argument of a curried function is called partial application. The resulting function has the first argument “fixed” and awaits the remaining arguments. This is sometimes called promotion: the function prefix applied to "Senior " promotes, yielding promote.

Mathematical intuition: the function x^y with y = 2 gives squaring; with y = 3 gives cubing; with y = 1 gives the identity function. Each is obtained by fixing the second argument.

Nesting of fun

The curried form nests fun expressions:

fun a -> fun b -> E

is read as: a function that takes a, and returns a function that takes b and computes E. In OCaml, -> associates to the right, so the type string -> string -> string means string -> (string -> string). Application associates to the left, so prefix "Senior " "Professor" means (prefix "Senior ") "Professor".

Curried shorthand syntax

OCaml provides a concise syntax for curried function definitions. The following two definitions are equivalent:

let prefix a b = a ^ b
(* val prefix : string -> string -> string = <fun> *)

let prefix = fun a -> fun b -> a ^ b
(* val prefix : string -> string -> string = <fun> *)

In general: let f x₁ ... xₙ = E is equivalent to:

fun x₁ -> ... -> fun xₙ -> E

Application uses the same syntax: f E₁ ... Eₙ means ((f E₁) ...) Eₙ.

Partial application

Partial application means supplying fewer arguments than a curried function expects, producing a new function with the remaining parameters.

let dub = prefix "Sir "
(* val dub : string -> string = <fun> *)

dub "Hamilton"
(* : string = "Sir Hamilton" *)

This is useful when fixing the first argument yields a function that is interesting in its own right.

Function lists and partial application

Curried functions interact naturally with lists of functions. Consider:

List.hd [dub; promote] "Hamilton"
(* : string = "Sir Hamilton" *)

Here List.hd extracts dub from the list of functions, and the resulting function is applied to "Hamilton". The type of this expression works because application associates to the left: (List.hd [dub; promote]) "Hamilton".

The idea of storing code in data structures and executing it later is fundamental to object-oriented programming.

Curried insertion sort

Passing an ordering predicate as a curried argument yields a general insertion sort:

let insort lessequal =
  let rec ins x = function
    | [] -> [x]
    | y::ys -> if lessequal x y then x :: y :: ys
               else y :: ins x ys
  in
  let rec sort = function
    | [] -> []
    | x::xs -> ins x (sort xs)
  in
  sort
(* val insort : ('a -> 'a -> bool) -> 'a list -> 'a list = <fun> *)

insort is a curried function: given an ordering predicate, it returns the sorting function itself. Usage:

insort (<=) [5; 3; 9; 8]  (* => [3; 5; 8; 9] *)
insort (>=) [5; 3; 9; 8]  (* => [9; 8; 5; 3] *)
insort (<=) ["bitten"; "on"; "a"; "bee"]  (* => alphabetical sort *)

The syntax (<=) turns the infix operator into a prefix function that can be passed as an argument. Passing (>=) yields a decreasing sort: this is valid because if ≤ is a partial ordering, then so is ≥.

The map functional

map is the “apply to all” functional. It applies a function to every element of a list, returning a list of results:

let rec map f = function
  | [] -> []
  | x::xs -> (f x) :: map f xs
(* val map : ('a -> 'b) -> 'a list -> 'b list = <fun> *)

The type ('a -> 'b) -> 'a list -> 'b list shows that map transforms a function on elements into a function on lists.

Examples

map (fun s -> s ^ "ppy") ["Hi"; "Ho"]
(* => ["Hippy"; "Hoppy"] *)

map (map double) [[1]; [2; 3]]
(* => [[2]; [4; 6]] *)

Without map, the first example would require writing a dedicated recursive function. map captures the recursion pattern once and for all.

Matrix transpose

A matrix can be represented as a list of rows, where each row is a list of elements:

[[a; b; c]; [d; e; f]]
(* represents:  a b c
                 d e f   *)

The transpose function uses map with hd and tl:

let rec transp = function
  | []::_ -> []
  | rows -> (map List.hd rows) :: (transp (map List.tl rows))
(* val transp : 'a list list -> 'a list list = <fun> *)

The first column becomes the first row of the result. Recursion transposes the remaining columns. This is a concise definition that would otherwise require separate helper function declarations.

Matrix multiplication

The dot product of two vectors is computed by a curried function:

let rec dotprod xs ys =
  match xs, ys with
  | [], [] -> 0.0
  | x::xs, y::ys -> (x *. y) +. (dotprod xs ys)
(* val dotprod : float list -> float list -> float = <fun> *)

Because dotprod is curried, it can be partially applied to a single row. The matrix product then uses map:

let rec matprod arows brows =
  let cols = transp brows in
  map (fun row -> map (dotprod row) cols) arows
(* val matprod : float list list -> float list list -> float list list = <fun> *)

The inner map (dotprod row) cols computes the dot product of one row of A with every column of B. The outer map repeats this for every row of A. This is a compact replacement for the traditional triple-nested loop, avoiding subscript errors entirely.

Predicates and functionals

A predicate is a boolean-valued function (type 'a -> bool). Three key functionals transform predicates:

exists: stop on first true

let rec exists p = function
  | [] -> false
  | x::xs -> (p x) || (exists p xs)
(* val exists : ('a -> bool) -> 'a list -> bool = <fun> *)

Returns true if at least one element satisfies p. The lazy || ensures short-circuit evaluation: as soon as a match is found, the rest of the list is not examined. Without this laziness, exists would always traverse the entire list.

all: stop on first false

let rec all p = function
  | [] -> true
  | x::xs -> (p x) && all p xs
(* val all : ('a -> bool) -> 'a list -> bool = <fun> *)

Returns true if every element satisfies p. The lazy && stops at the first counterexample.

filter: return matching elements

let rec filter p = function
  | [] -> []
  | x::xs -> if p x then x :: filter p xs
            else filter p xs
(* val filter : ('a -> bool) -> 'a list -> 'a list = <fun> *)

Returns the list of all elements satisfying the predicate.

Applications

Membership

let member y xs = exists (fun x -> x = y) xs
(* val member : 'a -> 'a list -> bool = <fun> *)

member tests whether y appears in xs using exists with an anonymous equality predicate.

Intersection

let inter xs ys = filter (fun x -> member x ys) xs
(* val inter : 'a list -> 'a list -> 'a list = <fun> *)

inter filters xs, keeping only those elements that also appear in ys.

Disjointness

let disjoint xs ys = all (fun x -> all (fun y -> x <> y) ys) xs
(* val disjoint : 'a list -> 'a list -> bool = <fun> *)

Returns true if the two lists share no common elements. The inner all checks that x is different from every element of ys; the outer all checks this for every x in xs.

Historical context

Alonzo Church’s λ-calculus gave a simple syntax (λ-notation) for expressing functions. It is the direct precursor of OCaml’s fun-notation. Church’s thesis states that λ-definable functions are precisely the effectively computable ones, equivalent in power to Turing machines.

Peter Landin (Queen Mary College, London) sketched the main features of functional programming languages in 1966. McCarthy’s Lisp, while historically important, initially interpreted variable binding incorrectly - an error that persisted for about twenty years. The λ-calculus has had a profound influence on the design of modern functional languages.

Two kinds of programs

Producer → Filter → Consumer pipeline

We can model a simple pipeline without full concurrency. The model is:

Producer → Filter → ... → Filter → Consumer

• The Producer outputs items as a stream.
• Filters transform the stream (perhaps consuming several items to produce one output).
• The Consumer takes elements as needed.

The Consumer drives the pipeline: nothing is computed except in response to demand for the next datum. Execution of filter stages is interleaved as needed. The programmer sets up data dependencies but has no clear idea of what happens when - creating an illusion of concurrency.

Unix analogy

Unix pipes (|) link processes together similarly. Data flows from one process to the next, with the consumer pulling data through the chain. In OCaml, lazy lists provide the same effect within a single program.

Why this matters

• Avoids computing values that are never consumed
• Handles potentially infinite data sources naturally
• Separates generation, transformation, and consumption concerns cleanly
• Particularly useful when a problem has many solutions but only a few are needed (e.g. making change, search problems)

The unit type

The primitive type unit has exactly one value, written (). It may be regarded as a 0-tuple. Its uses include:

• Placeholder in data structures (e.g. a unit-valued dictionary represents a set)
• Argument to delay evaluation: fun () -> E
• Result of procedures that perform side effects

The lazy list type

type 'a seq =
  | Nil
  | Cons of 'a * (unit -> 'a seq)

A sequence is either empty (Nil) or a Cons cell containing a head value and a tail function of type unit -> 'a seq. The tail is not evaluated until the function is called - this is delayed evaluation, which is weaker than full lazy evaluation but sufficient for our purposes.

Key operations

let head (Cons (x, _)) = x

let tail (Cons (_, xf)) = xf ()

• head returns the first element immediately.
• tail forces evaluation by calling the tail function xf() with the unit argument (). The () serves as a placeholder - we need some argument to trigger evaluation, but no actual information is required.

Delaying evaluation

The expression fun () -> E delays evaluation of E: E is not computed until the function is called, even though the only possible argument is (). This is the key mechanism for implementing laziness in a strict language like OCaml.

The pattern

Every force must be enclosed within a delay for a function to remain lazy:

(* Correct - lazy *)
Cons (x, fun () -> ... xf () ...)

(* Risky - may force the whole sequence *)
... xf () ...

A force (xf()) not protected by a delay runs the risk of evaluating the entire sequence, defeating the purpose of laziness.

OCaml vs Haskell

Haskell uses lazy evaluation everywhere - even if-then-else can be a function and all lists are lazy. OCaml provides delayed evaluation through the unit -> 'a thunk pattern, which is a good compromise between performance and expressiveness. The result of forcing is not memoised in OCaml (unlike Haskell), so repeated forcing recomputes the value.

Generating infinite sequences: from

let rec from k = Cons (k, fun () -> from (k + 1))
(* val from : int -> int seq = <fun> *)

from k produces the infinite sequence k, k+1, k+2, … . Execution terminates because the recursive call from (k+1) is enclosed within fun () -> .... Without this delay, the recursion would be unbounded and the function would never return.

Interactive exploration

let it = from 1
(* val it : int seq = Cons (1, <fun>) *)

let it = tail it
(* val it : int seq = Cons (2, <fun>) *)

let it = tail it
(* val it : int seq = Cons (3, <fun>) *)

OCaml displays the tail of a sequence as <fun>. Each call to tail generates the next element.

Consuming a sequence: get

let rec get n s =
  match n, s with
  | 0, _            -> []
  | n, Nil          -> []
  | n, Cons (x, xf) -> x :: get (n - 1) (xf ())
(* val get : int -> 'a seq -> 'a list = <fun> *)

get n s extracts the first n elements as an ordinary list. The call xf() forces evaluation of the next element. If n is negative, it takes all elements (terminating only for finite sequences).

Evaluation trace

Consider get(2, from 6):

get(2, from 6)
=> get(2, Cons(6, fun () -> from (6+1)))
=> 6 :: get(1, from (6+1))
=> 6 :: get(1, Cons(7, fun () -> from (7+1)))
=> 6 :: 7 :: get(0, Cons(8, fun () -> from (8+1)))
=> 6 :: 7 :: []
=> [6; 7]

Note: three elements are computed (6, 7, and 8), even though only two were requested. Our implementation is slightly too eager - the tail of the last Cons is constructed before get checks that n = 0. A more complex type declaration could avoid this. In a truly lazy language like Haskell, only the demanded elements would be computed.

appendq: lazy concatenation

let rec appendq xq yq =
  match xq with
  | Nil -> yq
  | Cons (x, xf) -> Cons (x, fun () -> appendq (xf ()) yq)
(* val appendq : 'a seq -> 'a seq -> 'a seq = <fun> *)

This is the lazy analogue of list append (@). It copies elements from xq until exhausted, then switches to yq.

Critical limitation

If xq is infinite, appendq never reaches yq. The second argument is silently lost. Concatenation of infinite sequences is not terribly useful for this reason.

interleave: fair combination

let rec interleave xq yq =
  match xq with
  | Nil -> yq
  | Cons (x, xf) -> Cons (x, fun () -> interleave yq (xf ()))
(* val interleave : 'a seq -> 'a seq -> 'a seq = <fun> *)

interleave exchanges the arguments in the recursive call. This means:

• First element comes from xq
• Second element comes from yq (the old second argument, now first)
• Third element comes from the rest of xq
• And so on, alternating

This is fair: no elements from either sequence are lost, even if both are infinite. Interleaving is the right way to combine two potentially infinite information sources into one.

The key pattern: delay around force

In both appendq and interleave, observe that each xf() (a force) is enclosed within fun () -> ... (a delay):

Cons (x, fun () -> appendq (xf ()) yq)

This is the standard recipe for maintaining laziness. A force not enclosed in a delay (as in the get function) will compute the next element immediately rather than on demand.

Comparison

filterq: lazy filtering

let rec filterq p = function
  | Nil -> Nil
  | Cons (x, xf) ->
      if p x then
        Cons (x, fun () -> filterq p (xf ()))
      else
        filterq p (xf ())
(* val filterq : ('a -> bool) -> 'a seq -> 'a seq = <fun> *)

filterq demands elements from the sequence until it finds one satisfying p. It contains a force (xf()) not protected by a delay in the else branch: if no element satisfies the predicate within a finite prefix, filterq will evaluate the rest before producing any output.

Behaviour with infinite sequences

If the input sequence is infinite and contains no element satisfying p, then filterq runs forever without producing any output. This is a natural consequence: the function cannot know that no matching element exists without examining every element, of which there are infinitely many.

iterates: generalised from

let rec iterates f x =
  Cons (x, fun () -> iterates f (f x))
(* val iterates : ('a -> 'a) -> 'a -> 'a seq = <fun> *)

iterates f x generates the infinite sequence:

x, f(x), f(f(x)), f(f(f(x))), …

This generalises from: from k is equivalent to iterates (fun n -> n + 1) k.

Exercise: map analogue for sequences

A lazy map functional would apply a function to every element of a sequence on demand. The key is to delay the recursive call:

let rec mapq f = function
  | Nil -> Nil
  | Cons (x, xf) -> Cons (f x, fun () -> mapq f (xf ()))

The fun () -> around the recursive call ensures that the tail is computed only when forced by the consumer.

The Newton-Raphson iteration

The Newton-Raphson method computes square roots. Given $a$, the iteration is:

$x_{\text{next}} = \frac{\frac{a}{x} + x}{2}$

In OCaml:

let next a x = (a /. x +. x) /. 2.0
(* val next : float -> float -> float = <fun> *)

Convergence on infinite sequences

iterates (next a) x₀ generates the infinite series of approximations. For $\sqrt{2}$ with $x_0 = 1.0$:

The last value is accurate to 10 significant digits. Convergence is quadratic: the number of correct digits roughly doubles each iteration.

within: stopping criterion

let rec within eps = function
  | Cons (x, xf) ->
      match xf () with
      | Cons (y, yf) ->
          if abs_float (x -. y) <= eps then y
          else within eps (Cons (y, yf))
(* val within : float -> float seq -> float = <fun> *)

within eps searches the lazy list for two consecutive approximations whose absolute difference is at most eps. When found, it returns the second (more accurate) value.

root: putting it together

let root a = within 1e-6 (iterates (next a) 1.0)
(* val root : float -> float = <fun> *)

root 2.0
(* : float = 1.41421356237309492 *)

This composes three small, interchangeable components:

1. next a - one iteration step
2. iterates (next a) 1.0 - infinite series of approximations
3. within 1e-6 - convergence test

The initial approximation of 1.0 is deliberately poor to demonstrate the method’s robustness.

Richardson extrapolation

This compositional approach to numerical computation has received attention in research literature. A recurring example is Richardson extrapolation, which improves the accuracy of numerical integration by combining results at different step sizes. The principle is the same: build numerical methods from small, combinable parts operating on sequences.

Two search strategies

When traversing a tree to find a solution node, two fundamental strategies exist:

Depth-first behaviour

DFS goes deep before going wide. At each node, the left subtree is explored completely before the right subtree. Preorder, inorder, and postorder traversals are all depth-first.

Problem: If the left subtree is infinite, DFS never reaches the right subtree. A solution sitting at the top of the right subtree will never be found.

Breadth-first behaviour

BFS visits nodes level by level horizontally. When visiting a node, it does not traverse its children until it has visited all other nodes at the current depth.

Implementation idea: Maintain a list of pending trees to visit. Initially contains just the root. Each step removes a tree from the front, and if it is a branch, adds its children to the back.

Problem: The space requirement grows exponentially with depth. At depth d, up to b^d nodes may be stored simultaneously.

When to use each

• DFS when the tree is finite, solutions are plentiful, and memory is constrained.
• BFS when the shortest path matters, or when the tree may be infinite/unbalanced.
• Neither is ideal for large/infinite search spaces - iterative deepening (see later) combines their strengths.

Implementation with lists and append

let rec nbreadth = function
  | [] -> []
  | Lf :: ts -> nbreadth ts
  | Br (v, t, u) :: ts ->
      v :: nbreadth (ts @ [t; u])
(* val nbreadth : 'a tree list -> 'a list = <fun> *)

nbreadth maintains a list of pending trees. It removes the first tree, and if it is a branch, appends its children to the end of the list.

Why this is inefficient

The expression ts @ [t; u] is the problem. @ copies its entire first argument to append two elements. At depth d, the list ts contains all remaining trees at the current depth plus subtrees already queued for the next depth - potentially hundreds or thousands of elements. Each append copies them all.

Performance evidence

On a full binary tree of depth 12 (containing 4095 labels):

For larger trees, the speedup would be even more dramatic. The naive version is O(n²) in the size of the pending list, while the queue-based version is O(n).

Why this matters

This is a classic example of how a poor choice of data structure (using append to simulate a queue) can catastrophically degrade performance. The algorithm is correct, but the implementation is wasteful. The fix is to use a proper queue data structure that supports efficient addition to the tail, which we develop next.