Tripos 2023 Paper 1 Question 1 — Worked Solution

Question: Sort elements by frequency using run-length encoding (RLE). An RLE representation has type ('a * int) list where the int is the repetition count.

let input1 = [4; 1; 3; 3; 2; 3; 1]
let input2 = ['a'; 'e'; 'i'; 'e'; 'o'; 'e'; 'i']

(a) Efficient list reversal [2 marks]

Define rev that reverses a list in O(n) time.

let rev xs =
  let rec rev_app xs acc =
    match xs with
    | [] -> acc
    | x :: rest -> rev_app rest (x :: acc)
  in
  rev_app xs []

Explanation: We use the standard accumulator technique from Lecture 3. rev_app xs acc reverses xs and prepends it to acc. Each element is consed onto the accumulator, so each step does O(1) work. Total: O(n) time, O(1) stack space (tail-recursive). This is the efficient rev introduced in the course — unlike nrev which uses @ and takes O(n^2).

(b) Sorting function [6 marks]

Define sort : ('a -> 'a -> int) -> 'a list -> 'a list using an algorithm of your choice.

Solution (using merge sort — O(n log n) worst-case):

let rec merge cmp l1 l2 =
  match l1, l2 with
  | [], l -> l
  | l, [] -> l
  | h1 :: t1, h2 :: t2 ->
      if cmp h1 h2 <= 0 then h1 :: merge cmp t1 l2
      else h2 :: merge cmp l1 t2

let rec take n = function
  | [] -> []
  | x :: xs -> if n > 0 then x :: take (n - 1) xs else []

let rec drop n = function
  | [] -> []
  | x :: xs -> if n > 0 then drop (n - 1) xs else x :: xs

let rec sort cmp = function
  | [] -> []
  | [x] -> [x]
  | xs ->
      let n = List.length xs / 2 in
      let left = sort cmp (take n xs) in
      let right = sort cmp (drop n xs) in
      merge cmp left right

Explanation: We implement top-down merge sort (Lecture 5). The comparator function returns ≤ 0 if the first argument should come before (or equal to) the second, and > 0 otherwise. merge combines two sorted lists in O(m+n) time. sort recursively splits the list in half (via take/drop), sorts each half, and merges. The recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n) in the worst case. The comparator parameter makes it polymorphic: we can sort by any ordering.

Alternative (quicksort — simpler but O(n^2) worst-case):

let rec sort cmp = function
  | [] -> []
  | x :: xs ->
      let smaller = List.filter (fun y -> cmp y x <= 0) xs in
      let larger = List.filter (fun y -> cmp y x > 0) xs in
      sort cmp smaller @ [x] @ sort cmp larger

Either approach is acceptable. The merge sort version is safer but requires take and drop.

(c) RLE encode and decode [6 marks]

let rle_encode xs =
  let rec go current count = function
    | [] -> [(current, count)]
    | x :: rest ->
        if x = current then go current (count + 1) rest
        else (current, count) :: go x 1 rest
  in
  match xs with
  | [] -> []
  | x :: rest -> go x 1 rest

let rle_decode =
  let rec repeat x n acc =
    if n <= 0 then acc
    else repeat x (n - 1) (x :: acc)
  in
  let rec go = function
    | [] -> []
    | (x, n) :: rest ->
        let repeated = repeat x n [] in
        repeated @ go rest
  in
  go

Better version of rle_decode (without @ for efficiency):

let rle_decode rle =
  let rec repeat x n acc =
    if n <= 0 then acc
    else repeat x (n - 1) (x :: acc)
  in
  let rec go acc = function
    | [] -> rev acc
    | (x, n) :: rest ->
        go (repeat x n acc) rest
  in
  go [] rle

Explanation: rle_encode assumes the input list is sorted (so equal elements are adjacent). It walks the list maintaining current (the element being counted) and count (how many times it’s been seen). When the element changes, it emits the pair and resets. The function runs in O(n) time where n is the list length.

rle_decode reverses the process: for each (x, n) pair, it produces n copies of x. The helper repeat builds the copies (with an accumulator to make it tail-recursive, though the result is reversed). We use rev at the end to correct the order. Total time is O(N) where N is the total number of elements in the decoded list. Type: val rle_encode : 'a list -> ('a * int) list and val rle_decode : ('a * int) list -> 'a list.

(d) Frequency sort [6 marks]

Define freq_sort that sorts elements in ascending order of their frequency of occurrence.

let freq_sort cmp xs =
  let sorted = sort cmp xs in
  let encoded = rle_encode sorted in
  let by_freq = sort (fun (_, c1) (_, c2) ->
    if c1 < c2 then -1
    else if c1 > c2 then 1
    else 0
  ) encoded in
  rle_decode by_freq

Explanation: The strategy has four steps:

1. Sort the original list by value (using cmp) so equal elements are adjacent and can be run-length encoded.
2. Encode the sorted list into RLE form: each pair (value, count).
3. Re-sort the RLE pairs by frequency (the count component), in ascending order. We write a comparator that compares the second element of each pair. This groups elements from least frequent to most frequent.
4. Decode the re-sorted RLE back into a flat list.

For input1 = [4; 1; 3; 3; 2; 3; 1]:

• After value-sort: [1; 1; 2; 3; 3; 3; 4]
• RLE: [(1,2); (2,1); (3,3); (4,1)]
• After frequency-sort: [(2,1); (4,1); (1,2); (3,3)] (frequency 1, then 2, then 3)
• Decode: [2; 4; 1; 1; 3; 3; 3]

This matches the required output. Elements with the same frequency keep their relative order from the value-sort step because sort is stable in our merge sort implementation (or we could add tie-breaking to the comparator). Time complexity: O(n log n) dominated by the two sorting steps. Space: O(n).