Performance horrors

John Meacham john at
Wed Aug 27 16:00:44 EDT 2008

On Wed, Aug 27, 2008 at 04:48:41PM +0100, David House wrote:
> 2008/8/27 Adrian Hey <ahey at>:
> > As does the O(n*(log n)) AVL based nub I just wrote.
> Care to share?
> 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.


John Meacham - ⑆⑆john⑈

More information about the Libraries mailing list