Proposal #2629: Data.List: Replace nub; add nubOrd, nubInt, nubWith

[David Roundy]

On Tue, Sep 30, 2008 at 11:58:07AM -0400, David Roundy wrote:
> On Tue, Sep 30, 2008 at 1:46 AM, Bart Massey wrote:
> >    Note, though, that one can easily imagine a nubAscii
> >    that is linear-time rather than the n log n time of
> >    nubOrd / nubInt, using a small bit vector to track the
> >    Chars.  Certainly nubBool has this property.  Hmm.
> >    What's our criterion for when the performance difference
> >    between two functions constitutes a practical semantic
> >    difference?  I'm claiming it's asymptotic complexity
> >    class, in which case (a) we should probably figure out how
> >    to expose some kind of nubFinite.  Or we could just take
> >    the position that in the vast universe of possible
> >    functions, our library cannot provide them all.  In
> >    which case (1b) nubWith is back in.  I guess I tend
> >    toward (1b).
> 
> Actually, the asymptotic complexity (measured in terms of list length)
> of nubOrd is identical to the asymptotic complexity of nubAscii,
> nubBool or nubFinite.  They differ by a constant factor of the log(#
> possible data values).

Incidentally, for data types with finite value ranges, nub itself
isn't bad, as it'd just O(n * # of values present).  So, for instance,
nub on a list of Bool is likely to be faster than nubOrd on a list of
bools, and it's certainly O(n)... I just ran a timing, and nub takes
about as long as length does.

David