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

Isaac Dupree isaacdupree at
Fri Oct 3 13:35:20 EDT 2008

David Roundy wrote:
> 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).

except for infinite possible data values, such as Integer or 
String -- then they don't differ by a constant factor of 
infinity!  (And the constant factor on, say, Int64 and 
higher could be a lot larger than some implementations might 
be able to make it, I'm not sure)


More information about the Libraries mailing list