Performance horrors

[Adrian Hey]

Christopher Lane Hinson wrote:
> 
>>> WDYT about using RULES to rewrite to nubOrd if an Ord context is
>>> available, as John Meacham mentioned?
>>>
>>> John: you said you were uneasy about changing the complexity of an
>>> algorithm using RULES, but this is exactly what list fusion does
>>> (albeit for space, not time).
>>
>> Indeed. and I am a little uneasy about that too :) not that I don't
>> think it is an excellent idea and reap the benefits of fast list
>> operations.. O(n^2) to O(n log n) just feels like a bigger jump to me
>> for some reason. I think in the end, the RULES are a good idea, but I
>> personally try to make which one I am using explicit when possible.
>> Hence making my ideas as to the time/space requirements for an operation
>> to both the compiler and a future reader of the code
> 
> 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

Regards
--
Adrian Hey