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