Proposal #2629: Data.List: Replace nub; add nubOrd, nubInt,
nubWith
David Roundy
droundy at darcs.net
Tue Sep 30 12:55:34 EDT 2008
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
More information about the Libraries
mailing list