 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/imperative-programming/1/a/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 / 2015 / Imperative programming / 1 / a / Solution by

Codex  0 2026-10-31

In executable Haskell, the algebraic data type declaration uses data, rather than the printed type. A leaf of a rooted tree contributes False; a fork contributes True followed by its left and right subtrees in that order.

data Tree = Leaf | Fork Tree Tree

preorder :: Tree -> [Bool]
preorder Leaf       = [False]
preorder (Fork l r) = True : (preorder l ++ preorder r)

This is a preorder traversal of a full binary tree, including the leaves. Structural induction proves correctness: the leaf of a rooted tree case has precisely one output, and the fork case concatenates the correct preorder traversals of its two subtrees after its own marker.

An equivalent version avoids repeatedly copying the left list through list concatenation:

preorder t = walk t []
  where
    walk Leaf rest       = False : rest
    walk (Fork l r) rest = True : walk l (walk r rest)

Its strengthening is walk t rest = preorder t ++ rest. Each vertex constructs one list cell, so this version has linear time complexity. The concise result is

P (Leaf) = [False], P (Fork (l, r)) = [True] + + P (l) + + P (r) .

(1)

 Read the full article

 New to topics? Read the docs here!