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

[Bart Massey]

I think that the easiest way to think about the asymptotic
complexity of the nub* functions is in terms of the length n
of the input list and the number of unique elements m in
that list, as I did in a previous posting.  My original
point in this thread, which I stated badly, is this: Since
array access is constant time, one can imagine an
implementation nubIx that has O(n) worst-case time on any Ix
datatype, regardless of m. This contrasts with the O(mn)
complexity of nub and the O(n log m) complexity of nubOrd on
values of type Ix.  It is true that for any fixed m any nub*
is O(n), but IMHO this fact is a bit misleading; we probably
want to think about the asymptotic complexity in m as well
as n to get a clear picture of what's going on.

    Bart Massey
    bart <at> cs.pdx.edu