From: libraries-bounces@haskell.org [mailto:libraries-bounces@haskell.org] On Behalf Of Neil Mitchell
Complexity theory plus the Eq context makes that inevitable. You can't have nub over Eq in anything less than O(n^2)
I was going to say I sure hope nobody uses this in real programs, but I thought I'd better check first and I see that darcs seems to use it in a few places. Hmm..
nub :: Ord a => [a] -> [a] nub = nubBy compare
Having nubOrd is a great idea, I even proposed it previously, but people disagreed with me. Propose it and add it by all means.
The name is... well, pessimal might be a bit strong, but few programmers would think to look for something called "nub". Personally, when I first looked for it I expected uniq or unique (because that's what the unix utility that does the same thing is called). Distinct (from SQL) is another name that occurred to me, but never nub... it's not even a synonym for unique: http://thesaurus.reference.com/browse/unique See the redefinition of nub as uniq here (which I assume is because John didn't know about nub): http://hackage.haskell.org/packages/archive/MissingH/1.0.0/doc/html/Data -List-Utils.html The folklore (such as it is) for uniq is that it is trivially defined like so (for lists):
uniq = map head . group . sort
and so perhaps is not worthy of library inclusion? BTW, is this a suitably performant definition, or would we benefit from a lower-level implementation? Alistair ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************