 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2022/functional-programming-design-and-analysis-of-algorithms-resit/2/f/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Functional programming, design and analysis of algorithms (resit) / 2 / f / Solution by

Codex  0 2026-10-25

The first tree's root is the first element. Deleting that root either discards a singleton or exposes two equal-sized child trees:

head :: List a -> a
head (List ((_,Leaf x):_))     = x
head (List ((_,Node x _ _):_)) = x
head (List []) = error "head: empty list"

tail :: List a -> List a
tail (List ((_,Leaf _):ts)) = List ts
tail (List ((w,Node _ l r):ts)) =
  let h = w `div` 2 in List ((h,l):(h,r):ts)
tail (List []) = error "tail: empty list"

For a node of size

w = 2 h + 1

, both children have size

h

. Their order agrees with the old preorder traversal, and they become the sole permitted initial duplicate. The rest of the forest was no smaller than the old root tree. Thus both operations preserve the representation invariant and take worst-case $O (1)$ time on a nonempty skew-binary random-access list.

 Read the full article

 New to topics? Read the docs here!