 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/d/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 / d / Solution by

Codex  0 2026-10-25

Only the first two trees need inspection:

cons :: a -> List a -> List a
cons x (List ((w,t):(v,u):ts))
  | w == v = List ((2*w+1, Node x t u):ts)
cons x (List ts) = List ((1, Leaf x):ts)

When the first sizes agree, place x above those two perfect binary trees. Its preorder traversal is x followed by the old two traversals. No further size-

w

tree can occur, so all remaining sizes are at least

2 w + 1

; equality creates at most the allowed initial duplicate. When the first sizes differ, adjoining a singleton is valid, including the case that the old first tree is also a singleton. These are exactly the two possible greedy representations after increasing the length by one. Each case creates a bounded number of constructors and inspects no tree interior, giving worst-case $O (1)$ time complexity. Existing trees are shared.

 Read the full article

 New to topics? Read the docs here!