Duncan Coutts wrote:
So can anyone break this hypothesis?
nub . sort = map head . group . sort
Just make Eq and Ord instances that are completely unrelated, say data Foo = Foo Int Int deriving Show instance Eq Foo where Foo a _ == Foo b _ = a == b instance Ord Foo where Foo _ a `compare` Foo _ b = a `compare` b example = [Foo 0 1, Foo 0 2, Foo 1 1] With these instances nub . sort does something well-defined; sort only uses `compare` and nub only uses (==). Note that Data.List.sort actually provides a stable sort. I don't know if that's specified anywhere, but it's true for both Data.List and for the Haskell report implementation of sort. The rule
nub . sort = map head . group . sort
on the other hand relies on a correspondence between Eq and Ord and breaks: > nub . sort $ example [Foo 0 1,Foo 1 1] > map head . group . sort $ example [Foo 0 1,Foo 1 1,Foo 0 2] More precisely the rule works iff a <= b && b <= c && a == c implies a == b. I'm not sure whether mismatching Eq and Ord [*] instances should be a programmer error, but if so this needs to be stated somewhere. Right now, Data.List has no such restriction. Bertram [*] Ideally, the correspondance should be that (a == b) == (a <= b && b <= a)