Christopher Lane Hinson
lane at downstairspeople.org
Wed Aug 27 17:09:36 EDT 2008
>> 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).
More information about the Libraries