Proposal #2629: Data.List: Replace nub;
add nubOrd, nubInt, nubWith
daveroundy at gmail.com
Tue Sep 30 11:58:07 EDT 2008
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).
More information about the Libraries