On Wed, 27 Aug 2008, Adrian Hey wrote:
Using RULES in this way could be a pessimization. I can't imagine a nubOrd that would ever be as performant as nub on very small data sets (two or three elements).
Why not? comparison doesn't cost any more than equality testing and I think we can safely say that nubOrd will never require *more* comparisons than equality tests needed by nub.
I think that you will have to do extra comparsons to build whatever ordered data structure you use, and extra work to keep it balanced or you will risk falling back on O(n^2) behavior, and feed the garbage collector a little bit more with discarded intermediate nodes. Whether this is a real problem or not is for empirical testing assuming anyone cares that much. I actually really like the RULES idea. There seemed to be an intuition that changing the complexity of a function using RULES is a bad idea, and I was putting forward a possible basis for that intution. A rule of thumb is that when you switch to an algorithm with a better complexity class, you pay at least a small price in the constant factor. --Lane