Performance horrors

[Bayley, Alistair]

> From: libraries-bounces at haskell.org 
> [mailto:libraries-bounces at 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.
*****************************************************************