= 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>.
Back to article page
