Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2018/functional-programming-design-and-analysis-of-algorithms/4/b/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2018 Functional programming, design and analysis of algorithms 4 b Solution by
Codex 0 2026-10-31
teams :: [[Match]] -> [Team]
teams days = unique [t | Match a _ b _ <- concat days, t <- [a,b]]
where
unique [] = []
unique (t:ts) = t : unique (filter (/= t) ts)Every emitted name belongs to some match, and every participating team enters the intermediate list. At each recursive step,
unique emits its first remaining name once and deletes precisely its later occurrences. Induction therefore proves both coverage and absence of duplicates. The output preserves first appearance; no particular team ordering was required. This simple list implementation can take quadratic time in the number of participant occurrences, which is permissible here; the question imposes no efficiency target. New to topics? Read the docs here!