Recursive data types

ITT8060 Advanced Programming · Autumn 2026

Tallinn University of Technology

Full prose version with runnable examples: notes.html

ITT8060

1 · From lists to trees

ITT8060

Lists

In Lecture 4, ICons expects one recursive argument (of type IntList):

type IntList = INil
             | ICons of int * IntList

Today we ask what happens when a constructor expects a number of such recursive arguments?

ITT8060

Binary trees

type 'a BinTree = Empty
                | Node of 'a BinTree * 'a * 'a BinTree

There are two constructors for constructing values of type 'a BinTree: one for an empty tree and one for a node. Constructors can be used as patterns to deconstruct values when matching.

The F# documentation calls them union cases; Empty and Node are their case identifiers, the names written in the declaration.

We can read the declaration as rules: Empty is a tree; if l and r are trees and x is a value, then Node (l, x, r) is a tree.

ITT8060

Drawing a tree

let small =
  Node (Node (Empty, 1, Empty), 2,
        Node (Empty, 3, Empty))

Here we have drawn every Empty.

From now on, we will omit them and the figures show the nodes only.

ITT8060

let leaf x = Node (Empty, x, Empty)

let t = Node (Node (leaf 2, 7, Empty),
              9,
              Node (leaf 13, 21, leaf 25))

Some terminology

The root of t is 9. Its left and right subtrees are rooted at 7 and 21, its children.

A leaf is a node whose both subtrees are empty: 2, 13 and 25.

size: the number of nodes. height: the number of nodes on a longest path from the root.

The empty tree has size 0 and height 0.

ITT8060

let rec size t =
  match t with
  | Empty -> 0
  | Node (l, _, r) -> size l + 1 + size r

let rec height t =
  match t with
  | Empty -> 0
  | Node (l, _, r) ->
      1 + max (height l) (height r)

Structural recursion

Recursive calls on recursive substructures (subtrees).

What are size t and height t?

6 and 3.

ITT8060

Not every tree is finite

Interpreting the constructors of 'a BinTree as (inductive) rules, we can only define finite trees. F# also accepts cyclic definitions:

let rec allOne = Node (allOne, 1, allOne)

allOne is an int BinTree: both subtrees are allOne itself, so the tree is cyclic and infinite.

What is size allOne?

It never returns: the recursion never reaches Empty (stack overflow).

Recall that let rec xs = 1 :: 2 :: xs is rejected.

Functions defined by structural recursion terminate on finite trees.

ITT8060

2 · Binary search trees

ITT8060

The search-tree condition

For every Node (l, x, r) in the tree: every value in l is less than x, and every value in r is greater than x.

Thus, a value occurs at most once.

The tree t is indeed a search tree.

ITT8060

let rec insert x t =
  match t with
  | Empty -> Node (Empty, x, Empty)
  | Node (l, y, r) ->
      match compare x y with
      | 0 -> t
      | c when c < 0 -> Node (insert x l, y, r)
      | _ -> Node (l, y, insert x r)

Insertion

Structural recursion; the constructors are used as patterns.

If x is already in t, then t itself is returned: no duplicates.

What type does F# infer for insert?

val insert:
  x: 'a -> t: 'a BinTree -> 'a BinTree
    when 'a: comparison

compare requires the comparison constraint.

ITT8060

let rec contains x t =
  match t with
  | Empty -> false
  | Node (l, y, r) ->
      if   x < y then contains x l
      elif x > y then contains x r
      else true

Membership

Only one path from the root is explored.

A comparison chain can also be written with if/elif.

What are contains 13 t and contains 8 t?

true and false.

ITT8060

BST invariant not enforced by the type

let bad = Node (leaf 5, 3, Empty)

bad type-checks, but it is not a search tree.

Is contains 5 bad true?

false: at 3 the search goes right, but 5 is on the left.

ITT8060

Preserving the invariant

A function f preserves an invariant if, for every x that satisfies the invariant, the result f x also satisfies the invariant.

In other words, f preserves the search tree invariant when, for every t that is a search tree, the result f t is also a search tree.

This means that if t is not a search tree, then we do not require anything from f t. ("garbage in, garbage out")

If f and g preserve the invariant and t is a search tree, then any sequence of f and g applications (e.g., f (g (g (f t)))) results in a search tree.

Task: implement a Set (Lecture 5) library that internally uses an 'a BinTree to represent the collection of elements as a search tree.

What should the library expose to its users and what should be kept hidden?

ITT8060

let rec inOrder t =
  match t with
  | Empty -> []
  | Node (l, x, r) ->
      inOrder l @ [x] @ inOrder r

In-order traversal

The left subtree, then the node, then the right subtree.

What is inOrder t?

[2; 7; 9; 13; 21; 25]

For a search tree, the result is sorted.

ITT8060

Removing the minimum

let rec removeMin t =
  match t with
  | Node (Empty, x, r) -> (x, r)
  | Node (l, x, r) ->
      let m, l' = removeMin l
      (m, Node (l', x, r))

let rec tryRemoveMin t =
  match t with
  | Empty -> None
  | Node (Empty, x, r) -> Some (x, r)
  | Node (l, x, r) ->
      tryRemoveMin l
      |> Option.map (fun (m, l') ->
           (m, Node (l', x, r)))

Left: F# warns that the match is incomplete, since Empty is not covered.

removeMin Empty fails at run time.

Right: total; the caller must handle None.

Which one would you use? Can we guarantee that t is not Empty?

ITT8060

let rec remove x t =
  match t with
  | Empty -> Empty
  | Node (l, y, r) ->
      match compare x y with
      | c when c < 0 -> Node (remove x l, y, r)
      | c when c > 0 -> Node (l, y, remove x r)
      | _ -> match tryRemoveMin r with
             | None -> l
             | Some (m, r') -> Node (l, m, r')

Removal

If the value is at a node, we put the smallest value of its right subtree in its place.

With tryRemoveMin, an empty right subtree is just the None case.

What is inOrder (remove 9 t)?

[2; 7; 13; 21; 25]

ITT8060

let rec map f t =
  match t with
  | Empty -> Empty
  | Node (l, x, r) ->
      Node (map f l, f x, map f r)

let neg = map (fun x -> -x) t

Mapping over a tree

map always preserves the shape of the tree but not necessarily the search tree invariant.

Is contains (-21) neg true?

false: the search for -21 goes left at -9, but -21 is on the right.

ITT8060

map sometimes preserves the invariant

A function f is monotone wrt a relation \(R\) if \(x \mathrel{R} y\) implies \((f\,x) \mathrel{R} (f\,y)\).

If t is a search tree and f is monotone wrt <, then map f t is a search tree.

Why do we require f to be monotone wrt <?

map f always preserves the shape of the tree.

map f where f is monotone (wrt <) also preserves the search-tree invariant.

ITT8060

A monotone function: doubling

t (left) and map (fun x -> 2 * x) t (right). Is the result a search tree?

Yes: fun x -> 2 * x is monotone with respect to <. Thus, if, for some values x and y in t, we have x < y, then we have f x < f y in the result.

In order: [4; 14; 18; 26; 42; 50].

ITT8060

Why the relation is `<`

t (left) and map (fun x -> x / 10) t (right). fun x -> x / 10 is monotone with respect to <=, but not <. Is the result a search tree?

No: the ordering is nondecreasing and allows duplicates.

In order: [0; 0; 0; 1; 2; 2].

The invariant is strict, so f must be monotone with respect to <.

ITT8060

let rec foldBack f t e =
  match t with
  | Empty -> e
  | Node (l, x, r) ->
      foldBack f l (f x (foldBack f r e))

Folding a tree

Specification: foldBack f t e should compute the same result as:

List.foldBack f (inOrder t) e

without building the intermediate list inOrder t.

What is foldBack (-) t 0?

-13.

ITT8060

`as` patterns

Inserting 3, 2 and 1 results in a chain; a rotation rebalances it:

let rotateRight t =
  match t with
  | Node (Node ((Node _ as ll), y, c), z, d) ->
      Node (ll, y, Node (c, z, d))
  | _ -> t

(Node _ as ll) checks that the grandchild is a Node and names it ll: reused, not rebuilt.

Recommendation: put an as pattern in parentheses.

The goal: look deeper into a value, and keep the part you inspected as it is.

ITT8060

3 · Expression trees

ITT8060

type Expr =
  | Const of float
  | X
  | Add of Expr * Expr
  | Sub of Expr * Expr
  | Mul of Expr * Expr
  | Div of Expr * Expr

let ex = Mul (X, Add (Const 2.0, X))

The type of expressions

Six constructors; as functions:

Const : float -> Expr
X : Expr
Add : Expr * Expr -> Expr

and Sub, Mul and Div like Add.

ex is a representation of \(x \cdot (2 + x)\).

Why does Expr have no constructor like Empty in 'a BinTree?

ITT8060

let rec eval e x =
  match e with
  | Const c -> c
  | X -> x
  | Add (e1, e2) -> eval e1 x + eval e2 x
  | Sub (e1, e2) -> eval e1 x - eval e2 x
  | Mul (e1, e2) -> eval e1 x * eval e2 x
  | Div (e1, e2) -> eval e1 x / eval e2 x

let ex = Mul (X, Add (Const 2.0, X))

Evaluation

Given a value for X, every expression denotes a number.

For e : Expr and x : float, evaluating e at x, eval e x, is the value of e with x for X.

What is eval ex 4.0?

24.0

ITT8060

let rec deriv e =
  match e with
  | Const _ -> Const 0.0
  | X -> Const 1.0
  | Add (e1, e2) -> Add (deriv e1, deriv e2)
  | Sub (e1, e2) -> Sub (deriv e1, deriv e2)
  | Mul (e1, e2) ->
      Add (Mul (deriv e1, e2),
           Mul (e1, deriv e2))
  | Div (e1, e2) ->
      Div (Sub (Mul (deriv e1, e2),
                Mul (e1, deriv e2)),
           Mul (e2, e2))

let ex = Mul (X, Add (Const 2.0, X))

Symbolic differentiation

With respect to X.

Structural recursion.

What is deriv ex?

Add (Mul (Const 1.0, Add (Const 2.0, X)),
     Mul (X, Add (Const 0.0, Const 1.0)))

ITT8060

The derivative as a tree

ex (left) and deriv ex (right).

The result could be simplified (for example, \(0 + y = y\), \(1 \cdot y = y\)).

eval (deriv ex) 4.0 is 10.0.

ITT8060

4 · Mutual recursion: file systems

ITT8060

A file system

A file system is a list of entries.

An entry is a file, or a directory: a name and a file system.

ITT8060

type FileSys = Entry list
and Entry =
  | File of string
  | Dir of string * FileSys

let d1 =
  Dir ("d1",
       [ File "a1"
         Dir ("d2",
              [ File "a2"
                Dir ("d3", [ File "a3" ]) ])
         File "a4"
         Dir ("d3", [ File "a5" ]) ])

Mutually recursive types

Each declaration mentions the other, so they are declared together, with and.

Without the name FileSys, Dir could take an Entry list.

What is the type of d1?

Entry

ITT8060

let rec namesFileSys fs =
  match fs with
  | [] -> []
  | e :: es -> namesEntry e @ namesFileSys es
and namesEntry e =
  match e with
  | File s -> [s]
  | Dir (s, fs) -> s :: namesFileSys fs

Mutually recursive functions

Functions, too, are declared together with and.

What is namesEntry d1?

["d1"; "a1"; "d2"; "a2"; "d3";
 "a3"; "a4"; "d3"; "a5"]

What is the pattern used in namesFileSys?

ITT8060

Summary

Recursive discriminated unions are trees.

The type definition determines the shape of the trees we can represent.

Today we saw binary trees, expression trees (four different binary nodes), and "file systems" where a node can have any number of children.

Types in F# are not expressive enough to enforce all invariants (search tree).

ITT8060

Homework and reading

Homework 4 is out this week.

Reading: Hansen & Rischel, Functional Programming Using F#, chapter "Finite trees".

Exercises for the lab: the Exercises section of notes.html.

ITT8060

Recursive data types

1 · From lists to trees

Lists

Binary trees

Drawing a tree

Some terminology

Structural recursion

Not every tree is finite

2 · Binary search trees

The search-tree condition

Insertion

Membership

BST invariant not enforced by the type

Preserving the invariant

In-order traversal

Removing the minimum

Removal

Mapping over a tree

map sometimes preserves the invariant

A monotone function: doubling

Why the relation is <

Folding a tree

as patterns

3 · Expression trees

The type of expressions

Evaluation

Symbolic differentiation

The derivative as a tree

4 · Mutual recursion: file systems

A file system

Mutually recursive types

Mutually recursive functions

Summary

Homework and reading

Why the relation is `<`

`as` patterns