New articles - OurBigBook.com

An empty binary search tree has zero nodes; a nonempty node contributes one in addition to the sizes of its two subtrees:

size :: STree a -> Integer
size = foldSTree (\left _ right -> 1 + left + right) 0

The answer is

∣ Empty ∣ = 0, ∣ Node l x r ∣ = 1 + ∣ l ∣ + ∣ r ∣

. The tree fold visits every node once, so this takes

Θ (n)

arithmetic operations for

n

nodes.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 4 / d / Solution by

Codex  0 2026-10-31

Use the empty list for an empty subtree, and join the left result, the current label and the right result:

flatten :: STree a -> [a]
flatten = foldSTree (\left x right -> left ++ (x : right)) []

Thus

flatten (Node l x r) = flatten (l) + + [x] + + flatten (r)

. This is an inorder traversal. By structural induction, each subtree produces its labels in order; the binary search tree invariant places every left label below

x

and every right label above

x

, proving that the whole result is increasing. The definition works for any binary-tree shape, although its result is sorted only when the ordering invariant holds. Repeated list concatenation can give quadratic cost on a left chain; the question asks for a tree fold definition, rather than an optimal traversal implementation.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 4 / c / Solution by

Codex  0 2026-10-31

A tree fold replaces Empty by a seed and Node by a combining function. The combining function receives the already folded left subtree, the node's label and the already folded right subtree:

foldSTree :: (b -> a -> b -> b) -> b -> STree a -> b
foldSTree combine empty Empty = empty
foldSTree combine empty (Node left x right) =
  combine (foldSTree combine empty left)
          x
          (foldSTree combine empty right)

Its polymorphic type signature is

(β \to α \to β \to β) \to β \to STree α \to β .

The result type need not be the label type: it may be a list, a number or another structure. No ordering constraint is needed because this tree fold follows constructors without comparing labels.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 4 / b / Solution by

Codex  0 2026-10-31

Follow the unique branch in which the new key could belong. At an equal key, keep the existing node so that duplicate insertion does not change the represented set:

insert :: Ord a => a -> STree a -> STree a
insert y Empty = Node Empty y Empty
insert y (Node left x right) =
  case compare y x of
    LT -> Node (insert y left) x right
    EQ -> Node left x right
    GT -> Node left x (insert y right)

The Haskell Ord class supplies the three-way comparison. Each visited nonempty node costs one such comparison; rebuilding a node preserves all untouched subtrees. The inserted key satisfies every comparison along its search path, so it obeys both the local and ancestor binary search tree inequalities.

For height of a binary tree

h

, the worst search costs

Θ (h) comparisons

when it reaches the bottom. With

n

existing nodes, a chain can require

n

comparisons, giving a worst case of

Θ (n)

. Under the standard random-insertion model, distinct keys arrive in a uniformly random order and the expected path length is

Θ (lo g (n + 1))

. Thus the usual average-case answer is

Θ (lo g n)

for growing

n

, but this expectation needs the stated distribution: an arbitrary unbalanced binary search tree has no logarithmic guarantee.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 4 / a / Solution by

Codex  0 2026-10-31

An empty constructor and a constructor containing a label and two subtrees give a polymorphic algebraic data type:

data STree a = Empty | Node (STree a) a (STree a)
  deriving (Eq, Show)

The binary search tree invariant is

every left label < x < every right label

at each Node left x right, together with the same invariant recursively in both subtrees. Labels are distinct because the representation is of a set. The declaration itself needs no ordering constraint; operations that compare labels require Ord a in their type signatures.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 3 / c / Solution by

Codex  0 2026-10-31

Compare frequencies in decreasing order and use lexicographic order on words to break ties. Implement merge sort explicitly, so no imported sorting routine is needed:

-- Entry, TextWord and Frequency are as in part (b).
before :: Entry -> Entry -> Bool
before (w, p) (v, q) = p > q || (p == q && w <= v)

sort :: [Entry] -> [Entry]
sort []  = []
sort [x] = [x]
sort xs  = merge (sort left) (sort right)
  where
    (left, right) = splitAt (length xs `div` 2) xs

merge :: [Entry] -> [Entry] -> [Entry]
merge [] ys = ys
merge xs [] = xs
merge xa@(x:xs) ya@(y:ys)
  | before x y = x : merge xs ya
  | otherwise  = y : merge xa ys

The merge algorithm step always emits the smaller key under the ordering

(- frequency, word)

. The unchosen heads cannot precede that emitted entry because each input is already sorted. It preserves all entries, and each call removes one head, so it terminates with exactly the sorted union of the inputs. Mathematical induction over the recursive splits establishes correctness of merge sort.

For

n

entries, splitting and merging cost

Θ (n)

per level, and there are

Θ (lo g n)

levels:

T (n) = T (⌊ n /2 ⌋) + T (⌈ n /2 ⌉) + Θ (n) = Θ (n lo g n) (n \geq 2) .

The base cases take constant time. This counts word comparisons as primitive operations, as in the question. If the maximum compared word length is

L

, the character-operation bound becomes

O (L n lo g n)

, in addition to frequency comparison costs.

For the supplied input, sort . count yields

[("baa",2),("sir",2),("yes",2),("any",1),("bags",1),("black",1),
 ("full",1),("have",1),("sheep",1),("three",1),("wool",1),("you",1)]

In particular, the secondary ordering places sir before yes, even though yes appears earlier in the original text. The

Θ (n lo g n)

requirement concerns sort; the simpler association list implementation of count has its own cost.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 3 / b / Solution by

Codex  0 2026-10-31

Normalize each word once by applying toLower to its characters. Maintain an association list whose keys are distinct normalized words and whose values are their frequencies:

import Data.Char (toLower)

type TextWord = String
type Text = [TextWord]
type Frequency = Integer
type Entry = (TextWord, Frequency)

count :: Text -> [Entry]
count = foldl addWord [] . map (map toLower)
  where
    -- Increment the unique matching key, or append a new key with count one.
    addWord :: [Entry] -> TextWord -> [Entry]
    addWord [] w = [(w, 1)]
    addWord ((v, n):rest) w
      | w == v    = (v, n + 1) : rest
      | otherwise = (v, n) : addWord rest w

After any input prefix, each normalized word seen so far occurs exactly once as a key, with its number of occurrences as value. This loop invariant holds initially for the empty association list. A step either increments the unique existing entry or introduces exactly one new entry, so mathematical induction proves

lookup w (count input) = Just (number of normalized occurrences of w)

for every word that occurs. In particular, Baa and baa contribute to the same key baa; the three frequency-two keys in the source example are baa, yes and sir.

The association list preserves first-occurrence order, although the specification allows any order here. For

t

input words and

d

distinct normalized words, it performs

O (t d)

key comparisons in the worst case. Character normalization costs the total input character count, and a string comparison can inspect multiple characters. Characterwise toLower supplies the intended case-insensitive comparison convention for the example; full Unicode case folding can require a different normalization policy.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 3 / a / Solution by

Codex  0 2026-10-31

A word can be a string, and the input text a list of those strings. Use names that avoid clashing with the Standard Prelude machine-word type Word:

type TextWord = String
type Text = [TextWord]

Thus

TextWord = String, Text = [TextWord]

. These are type synonyms, so ordinary string and list operations remain available without wrapping or unwrapping constructors. They describe input that has already been tokenized; punctuation and word boundaries do not need a separate treatment here.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 2 / e / ii by

Codex  0 2026-10-31

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 2 / e / i by

Codex  0 2026-10-31

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 2 / d / Solution by

Codex  0 2026-10-31

Set both

\oplus

and

\otimes

equal to list concatenation, with

a = []

. Associativity gives xs ++ (ys ++ zs) = (xs ++ ys) ++ zs, which is equation (1). The two identity laws give xs ++ [] = [] ++ xs, which is equation (2). Part (b) therefore yields

concat :: [[a]] -> [a]
concat = foldl (++) []

Thus

concat = foldl (+ +) []

on finite lists. The argument order is unchanged: the accumulator is the already concatenated prefix, and the next inner list is appended to its right. This preserves the order but repeatedly copies that prefix.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 2 / c / Solution by

Codex  0 2026-10-31

Use list concatenation as the combining operation and the empty list as the seed:

concat :: [[a]] -> [a]
concat = foldr (++) []

For three inner lists, this constructs xs ++ (ys ++ (zs ++ [])), preserving the elements' original order. The concise answer is

concat = foldr (+ +) []

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 2 / b / Solution by

Codex  0 2026-10-31

Again use structural induction on the finite list. At [], both the right fold and the left fold return the seed

a

. If they agree on zs, then

foldr (\oplus) a (z : zs) = z \oplus foldr (\oplus) a zs = z \oplus foldl (\otimes) a zs = foldl (\otimes) (z \oplus a) zs = foldl (\otimes) (a \otimes z) zs = foldl (\otimes) a (z : zs) .

The third line uses part (a); the fourth uses equation (2). Thus the left-right fold equivalence is

foldr (\oplus) a xs = foldl (\otimes) a xs .

(2)

This is a statement about values on finite, total inputs. It does not assert equal evaluation costs or equal behaviour on infinite lists.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 2 / a / Solution by

Codex  0 2026-10-31

Use structural induction on the finite list xs, strengthening the induction hypothesis to hold for every accumulator value

y

. For the empty list, the defining equation of the left fold gives

x \oplus foldl (\otimes) y [] = x \oplus y = foldl (\otimes) (x \oplus y) [] .

For the inductive step, suppose the identity holds for the tail zs and every accumulator. Expand the first left fold, apply the induction hypothesis at accumulator

y \otimes z

, and then use the supplied compatibility law:

x \oplus foldl (\otimes) y (z : zs) = x \oplus foldl (\otimes) (y \otimes z) zs = foldl (\otimes) (x \oplus (y \otimes z)) zs = foldl (\otimes) ((x \oplus y) \otimes z) zs = foldl (\otimes) (x \oplus y) (z : zs) .

(2)

Hence

x \oplus foldl (\otimes) y xs = foldl (\otimes) (x \oplus y) xs .

(3)

Only equation (1) is needed for this part; the seed condition in equation (2) enters the next proof. Quantifying over the accumulator is essential because the recursive call changes it.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 1 / c / Solution by

Codex  0 2026-10-31

Represent Pascal's triangle by an infinite outer lazy list, each of whose elements is one finite row. Pad the preceding row with zero on its left and on its right, then add corresponding entries:

pascal :: [[Integer]]
pascal = iterate next [1]
  where
    -- Padding supplies the two boundary entries as well as the interior sums.
    next :: [Integer] -> [Integer]
    next row = zipWith (+) (0 : row) (row ++ [0])

Here iterate next [1] begins [[1],[1,1],[1,2,1],[1,3,3,1],...]. Every call to next receives a finite row, so its final zero is reachable. Lazy evaluation produces any requested finite prefix without trying to finish the infinite outer list.

Indexing rows and columns from zero, Pascal's rule says

pascal_{n} = [(0 n), (1 n), \dots, (n n)], (j n + 1) = (j - 1 n) + (j n) .

Take out-of-range binomial coefficients to be zero. The seed is the zeroth row, and the padded addition implements this identity at every position, including the two boundaries. Mathematical induction therefore proves every generated row correct. Using unbounded integers prevents overflow. Generating rows zero through

r

takes

Θ (r^{2})

arithmetic operations, with additional bit costs as the binomial coefficients grow.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 1 / b / ii by

Codex  0 2026-10-31

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 1 / b / i by

Codex  0 2026-10-31

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 1 / a / Solution by

Codex  0 2026-10-31

The map function changes each element of a list while preserving its order and length. List concatenation removes one level of nesting. Currying changes a function on a pair into a function taking its two arguments separately; uncurrying reverses this conversion:

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs

concat :: [[a]] -> [a]
concat []       = []
concat (xs:xss) = xs ++ concat xss

curry :: ((a, b) -> c) -> a -> b -> c
curry f x y = f (x, y)

uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry f (x, y) = f x y

These polymorphic type signatures impose no numerical, equality or ordering constraints: the definitions only inspect list or pair structure and apply a supplied function. In particular,

curry (f) x y = f (x, y), uncurry (g) (x, y) = g x y .

The recursive equations describe the two possible list constructors, so they also explain how the empty case terminates each finite computation.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Discrete mathematics, probability and continuous mathematics / 9 / c / Solution by

Codex  0 2026-10-31

Complete the square in the transformation:

Y = X (2 - X) = 1 - (X - 1)^{2} .

Since

0 < X < 2

almost surely,

0 < Y \leq 1

. For

0 \leq y < 1

, put

r = 1 - y

. The event

Y > y

is equivalent to

1 - r < X < 1 + r

. Integrating the given probability density function over both branches at once gives the survival function

P (Y > y) = \int_{1 - r}^{1 + r} \frac{x}{2} d x = \frac{( 1 + r ) ^{2} - ( 1 - r ) ^{2}}{4} = r .

(2)

Thus, including the tails,

P (Y > y) = ⎩ ⎨ ⎧ 1 1 - y 0 y < 0, 0 \leq y < 1, y \geq 1.

(3)

The cumulative distribution function on

(0, 1)

1 - 1 - y

. Differentiation gives

f_{Y} (y) = ⎩ ⎨ ⎧ \frac{1}{2 1 - y} 0 0 < y < 1, otherwise .

(4)

Both inverse branches matter:

x = 1 \pm 1 - y

. The endpoint divergence is integrable, and

P (Y = 1) = P (X = 1) = 0

, so no endpoint atom is needed.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Discrete mathematics, probability and continuous mathematics / 9 / b / ii by

Codex  0 2026-10-31