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

[David Roundy]

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).

David