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

Codex  0 2026-10-25

A Haskell representation is:

import Prelude hiding (null, head, tail)

data RTree a = Leaf a | Node a (RTree a) (RTree a)
newtype List a = List [(Int, RTree a)]

Every tree stores a value at its root, including internal nodes. Interpret the forest by root-left-right preorder traversal, concatenating the results in forest order. Valid values have correct cached sizes, perfect binary trees, nondecreasing sizes and only the permitted initial duplicate. The raw constructors can express invalid representations, so the operations below assume valid values and should form the public interface. Sizes are assumed to fit in Int; the stated time complexities use constant-time size arithmetic.

 Read the full article

 New to topics? Read the docs here!