Tripos 2021 Paper 1 Question 1 — Worked Solution

Question: Sequences (lazy lists) and trees with integer elements.

Given definitions:

type iseq = Nil
  | Cons of int * (unit -> iseq)

type itree = Leaf of int
  | Branch of itree * itree

(a) Merge two ascending sequences [5 marks]

Write merge2 that takes two ascending sequences and produces an ascending sequence of all elements.

Solution:

let rec merge2 s1 s2 =
  match s1, s2 with
  | Nil, _ -> s2
  | _, Nil -> s1
  | Cons (x, xf), Cons (y, yf) ->
      if x <= y then
        Cons (x, fun () -> merge2 (xf ()) s2)
      else
        Cons (y, fun () -> merge2 s1 (yf ()))

Explanation: We pattern-match on both sequences simultaneously. If either is Nil, we return the other (this covers both base cases). When both are non-empty, we compare the heads. The smaller head is emitted, and the tail is wrapped in fun () -> to delay the recursive call — this preserves laziness so elements are only computed on demand. The sequence with the larger head is passed through untouched (not forced), since its head may still be needed in later comparisons. Each step does constant work, so accessing the first n elements takes O(n) time — the same asymptotic cost as merging two ordinary sorted lists.

(b)(i) Sequence equality [5 marks]

Define equal_seq that compares two sequences for equality (corresponding elements equal).

Solution:

let rec equal_seq s1 s2 =
  match s1, s2 with
  | Nil, Nil -> true
  | Cons (x, xf), Cons (y, yf) ->
      x = y && equal_seq (xf ()) (yf ())
  | _ -> false

Explanation: The function forces both sequences element by element. If both are Nil simultaneously, they are equal. If one is Nil and the other is Cons, they have different lengths — unequal. If both are Cons, we check the heads for equality and then recursively compare the tails. The && operator is short-circuiting: if x = y is false, we return false immediately without forcing the tails. We force tails with xf () and yf () only when heads match. Since we must examine each pair of corresponding elements, the time complexity is O(n) where n is the length of the shorter sequence (or infinite if they match forever).

(b)(ii) Non-terminating equality [3 marks]

Define sequences s1 and s2 for which equal_seq s1 s2 does not terminate.

Solution:

let rec s1 = Cons (1, fun () -> s1)
let rec s2 = Cons (1, fun () -> s2)

Here s1 and s2 are infinite sequences of all 1s. The call equal_seq s1 s2 never terminates because every pair of corresponding elements is equal, so equal_seq forces another pair, which is also equal, and so on forever. The function attempts to verify equality of the entire infinite sequence, which is impossible without additional information.

Alternatively, any two infinite sequences that are element-wise equal will cause non-termination. For instance:

let rec s1 = Cons (1, fun () -> Cons (2, fun () -> s1))
let rec s2 = Cons (1, fun () -> Cons (2, fun () -> s2))

Both alternate 1, 2, 1, 2, ... — equal_seq s1 s2 will loop forever checking matching 1s and 2s.

(c)(i) Computing the fringe of a tree [5 marks]

Define fringe that returns the left-to-right sequence of leaf values. Type: val fringe : itree -> iseq.

Solution:

let rec fringe t =
  match t with
  | Leaf v -> Cons (v, fun () -> Nil)
  | Branch (left, right) ->
      appendq (fringe left) (fringe right)

and appendq s1 s2 =
  match s1 with
  | Nil -> s2
  | Cons (x, xf) -> Cons (x, fun () -> appendq (xf ()) s2)

Explanation: The fringe of a Leaf is a one-element sequence followed by Nil. For a Branch, we need to concatenate the fringes of the left and right subtrees. We use a helper appendq that lazily concatenates two sequences — it forces the first sequence element by element, wrapping each recursive call in fun () -> to preserve laziness. Once the first sequence is exhausted, it returns the second. This ensures that accessing fringe elements on demand does not force the entire tree traversal at once. The type is val fringe : itree -> iseq as required.

(c)(ii) Comparing fringes of two trees [2 marks]

Write equal_fringes that determines whether two trees have equal fringes.

Solution:

let equal_fringes t1 t2 =
  equal_seq (fringe t1) (fringe t2)

Explanation: We simply compute the fringe of each tree and compare sequences using equal_seq. Thanks to laziness, we only compute as much of each fringe as needed to find a difference. If the fringes differ at position k, we compute only the first k+1 elements of each fringe. This is efficient because we do not materialise entire fringes into lists — we compare on demand.