Lecture 6 — Recursive data types

From lists to trees

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?

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.

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.

Some terminology

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

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

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.

Structural recursion

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)

Recursive calls on recursive substructures (subtrees).

What are size t and height t?

let sizeT = size t
let heightT = height t

6

3

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. F# Interactive prints it as

val allOne: int BinTree = Node (..., 1, ...)

What is size allOne?

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

> size allOne;;
Stack overflow.

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

error FS0260: Recursive values cannot appear directly as a construction
of the type 'List`1' within a recursive binding. This feature has been
removed from the F# language. Consider using a record instead.

Functions defined by structural recursion terminate on finite trees.

Binary search trees

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.

Insertion

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)

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.

Membership

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

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?

let contains13 = contains 13 t
let contains8 = contains 8 t

true

false

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?

let containsBad = contains 5 bad

false

At 3 the search goes right, but 5 is on the left.

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?

In-order traversal

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

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

What is inOrder t?

let inOrderT = inOrder t

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

For a search tree, the result is sorted. "Garbage in, garbage out": inserting into bad gives a tree whose in-order list is not sorted.

let inOrderBad4 = inOrder (insert 4 bad)

[5; 3; 4]

Removing the minimum

// Deliberate warning FS0025: Empty is not covered.
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))

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

warning FS0025: Incomplete pattern matches on this expression. For example,
the value 'Empty' may indicate a case not covered by the pattern(s).

removeMin Empty fails at run time:

> removeMin (Empty: int BinTree);;
Microsoft.FSharp.Core.MatchFailureException: The match cases were incomplete

The second version is total; the caller must handle None:

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)))

let minOfEmpty = tryRemoveMin (Empty: int BinTree)

None

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

Removal

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')

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)?

let removed9 = inOrder (remove 9 t)

[2; 7; 13; 21; 25]

Mapping over a tree

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

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

Is contains (-21) neg true?

let containsNeg = contains (-21) neg

false

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

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.

A monotone function: doubling

map (fun x -> 2 * x) t is drawn below. Is the result a search tree?

let doubledTree = map (fun x -> 2 * x) t
let doubled = inOrder doubledTree

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]

Why the relation is <

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

let tenthsTree = map (fun x -> x / 10) t
let tenths = inOrder tenthsTree

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 <.

The condition is sufficient, not necessary: f only needs to be monotone on the values in the tree. fun x -> x * x is not monotone with respect to < on all integers, but it is on the positive values of t:

let squares = inOrder (map (fun x -> x * x) t)

[4; 49; 81; 169; 441; 625]

Folding a tree

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

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?

let foldT = foldBack (-) t 0

-13

The specification gives the same:

let foldList = List.foldBack (-) (inOrder t) 0

-13

as patterns

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

let chain = Empty |> insert 3 |> insert 2 |> insert 1

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

let rotated = rotateRight chain

(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.

The mirror image rotates a chain leaning right. Here the parentheses are needed: inside a tuple, as names everything to its left.

let rightChain = Empty |> insert 1 |> insert 2 |> insert 3

let rotateLeft t =
  match t with
  | Node (a, x, Node (b, y, (Node _ as rr))) ->
      Node (Node (a, x, b), y, rr)
  | _ -> t

let rotatedLeft = rotateLeft rightChain = Node (leaf 1, 2, leaf 3)

true

Without the parentheses, rr would name the whole tuple (b, y, Node _):

| Node (a, x, Node (b, y, Node _ as rr)) ->
error FS0727: This union case expects 3 arguments in tupled form, but
was given 1. The missing field arguments may be any of:
    'a
    'a BinTree

Expression trees

The type of expressions

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))

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?

Evaluation

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

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?

let evalEx = eval ex 4.0

24.0

Symbolic differentiation

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))

With respect to X. Structural recursion.

What is deriv ex?

let derivEx = deriv ex

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

The derivative as a tree

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

What is eval (deriv ex) 4.0?

let slopeEx = eval (deriv ex) 4.0

10.0

Mutual recursion: file systems

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.

Mutually recursive types

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" ]) ])

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?

val d1: Entry =
  Dir
    ("d1",
     [File "a1"; Dir ("d2", [File "a2"; Dir ("d3", [File "a3"])]); File "a4";
      Dir ("d3", [File "a5"])])

Mutually recursive functions

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

Functions, too, are declared together with and.

What is namesEntry d1?

let namesD1 = namesEntry d1

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

What is the pattern used in namesFileSys?

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).

Homework and reading

Homework 4 is out this week. Reading: Hansen & Rischel, Functional Programming Using F#, chapter "Finite trees".

Exercises

Exercise 1: checking the search-tree condition

inBounds lb t ub checks that every value in t lies strictly between lb and ub, and that t is a search tree. Going into the left subtree, the value at the node becomes the new upper bound; going into the right subtree, it becomes the new lower bound. Every node is visited at most once.

let rec inBounds (lb: 'a) (t: 'a BinTree) (ub: 'a) : bool =
  match t with
  | Empty -> true
  | Node (l, x, r) ->
    lb < x && x < ub
    && inBounds lb l x
    && inBounds x r ub

For int trees, the smallest and the largest int serve as the initial bounds:

let isBst t =
  inBounds System.Int32.MinValue t System.Int32.MaxValue

let isBstT = isBst t
let isBstBad = isBst bad
let isBstDuplicate = isBst (Node (Empty, 2, leaf 2))

true

false

false

isBst has two problems.

A tree with a single node is always a search tree, but a tree holding System.Int32.MinValue is rejected: no int is smaller than it.

let isBstMin = isBst (leaf System.Int32.MinValue)

false

isBst works only for int trees. For another element type we would need its smallest and largest values, and a type such as string has no largest value:

> isBst (leaf "a");;
error FS0001: This expression was expected to have type
    'int'
but here has type
    'string'

(a) Define a function

bounds : 'a option -> 'a BinTree -> 'a option -> bool

that checks the same condition as inBounds, but where a bound may be missing: None as the lower bound means that there is no lower bound, and None as the upper bound means that there is no upper bound.

(b) Define isBst' : 'a BinTree -> bool using bounds, without giving any concrete initial bound. For example:

• isBst' t is true;
• isBst' bad is false;
• isBst' (Node (Empty, 2, leaf 2)) is false;
• isBst' (leaf System.Int32.MinValue) is true;
• isBst' (leaf "a") is true: isBst' works for every element type that supports comparison.

Exercise 2: positions

The function tryItem returns the element at a given index of a list. It recurses on the index as on a natural number, and it corresponds to List.tryItem.

let rec tryItem (n: int) (xs: 'a list) : 'a option =
  match n, xs with
  // a negative index is not a position in any list
  | n, _ when n < 0 -> None
  // the index is a position, but this list is too short
  | _, [] -> None
  | 0, x :: _ -> Some x
  | n, _ :: xs' -> tryItem (n - 1) xs'

let item2 = tryItem 2 [10; 20; 30]
let item5 = tryItem 5 [10; 20; 30]
let itemMinus1 = tryItem (-1) [10; 20; 30]

Some 30

None

None

tryItem and List.tryItem agree on every index from -2 to 5:

let tryItemAgrees =
  [-2 .. 5]
  |> List.forall (fun n ->
    tryItem n [10; 20; 30] = List.tryItem n [10; 20; 30])

true

A position in a tree describes how to get from the root to a node.

(a) Define a type for positions in a binary tree ('a BinTree).

(b) Define a function

tryLookup : <your position type> -> 'a BinTree -> 'a option

tryLookup p t is Some x if the position p leads to a node of t holding x, and None if it does not. For the search tree t:

• the root gives Some 9;
• right, then left gives Some 13;
• left, left, then left again gives None.

(c) A list is a tree that leans to the right (lecture 4). Define a type for positions in a list in which the -1 case of tryItem cannot be represented: every value of your type must be a position that some list has. Then define

tryLookupList : <your position type> -> 'a list -> 'a option

with the same results as tryItem for every position that exists.

(d) Define a function

positions : 'a BinTree -> <your position type> list

that returns every position p for which tryLookup p t is not None, without duplicates and in any order. If your position type is P, the result has type P list. To check your answer:

• every position returned gives Some with tryLookup;
• the number of positions is size t.

Exercise 3: describing positions in a list

A value of the following type describes positions in a list:

type Sel =
  | Here
  | Next
  | Seq of Sel * Sel
  | Star of Sel

A selector is applied to a list and selects some of its elements:

• Here selects the head of the list.
• Next selects the head of the tail of the list.
• Seq (a, b) selects, for every element that a selects, what b selects from the list that starts at that element.
• Star a selects the head of the list, and what Seq (a, Star a) selects.

You may assume that in every Star a, the selector a never selects the head of the list it is applied to: each iteration moves at least one step. If a selector breaks this, your functions may return anything or never return ("garbage in, garbage out").

Both functions below have the type Sel -> 'a list -> 'a list. They return the selected elements in list order, each selected element once, even when it can be reached in several ways. Equal values at different places are different elements:

Star Next applied to [1; 1; 1] gives [1; 1; 1].

(a) Define selectByDesc by recursion on the selector: one case for each constructor.

(b) Define selectByList by recursion on the list. For a list x :: xs, answer two questions:

• Should x be selected?
• Which elements of xs should be selected? This is again a selection from a list, but no longer by the original selector, and there may be several possible "futures". How should we represent a number of possible futures?

Things to watch:

• a Seq (a, b) whose first part a is already finished at x;
• a selector that has no future at all;
• the same future arising in more than one way.

(c) Run both functions on Seq (Star Next, Star Next) and a long list. How often does each function visit an element? How large does the representation of the futures in selectByList get? When would you prefer one recursion over the other? How would you improve the two functions, for example by keeping the representation of the possible futures more compact?