= Solution
Choose the first unclassified element as the next <equivalence class representative>:
``
equiv :: Eq a => [a] -> [[a]]
equiv [] = []
equiv (x:xs) = (x:same) : equiv rest
where ~(same,rest) = partition (== x) xs
``
Assume the `Eq` instance is an <equivalence relation>. The <stable list partition> collects every later occurrence equivalent to `x`, and `rest` contains none of that <equivalence class>. <Induction> therefore gives exactly one group per class, preserving order within each group and ordering groups by their first occurrence. For $d$ distinct classes, each input element is tested against at most $d$ representatives: the cost is $O(nd)$ and \b[$\Theta(n^2)$ in the all-distinct worst case]; a single class takes $\Theta(n)$.
The <equality-only grouping lower bound> shows that this worst case is unavoidable in the unrestricted equality-oracle model. On an all-distinct input, an untested pair could instead be equal without changing any observed comparison. Certifying that all $n$ elements belong to different classes therefore requires all $\binom n2$ pairwise <equality tests>.
Back to article page
