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

Retain the first element, filter all its further occurrences out of the tail, and recurse:

removedup :: Eq a => [a] -> [a]
removedup []     = []
removedup (x:xs) = x : removedup (filter (/= x) xs)

The boxed specification is $\boxed{\text{each distinct input value occurs once, in first-occurrence order}}$. The Haskell type class Eq is needed for comparing values. Structural induction on a finite list proves duplicate removal: filtering removes every further x, and the recursive result contains each remaining distinct value exactly once. In the worst case of all distinct values, successive filters give quadratic time complexity.