If a Haskell expert (e.g., he authored hdirect -- an IDL compiler and interface with Win32 COM -- sadly defunct now) makes this kind of mistake, how are mere mortals supposed to reason about algorithmic efficiency?
edit: http://www.reddit.com/r/haskell/comments/1sh67u/the_reason_w... This comment by the patch author indicates that actually tracking it down was a fairly straightforward profiling job.
It'd be interesting to think how one could encode performance characteristics into equations.
C makes performance easy and correctness hard. Haskell makes correctness easy and performance hard.
The trick is, in most programs, you only need performance for a tiny subset of the program. You need correctness throughout the whole program.
We have to bridge that gap:
1) Either use a compiler that hides away the operational details
2) Or use a language that directly maps to the operational semantics, but then is necessarily far away from the denotational ones
That's not really an interesting property of Haskell, though. You can always write correct but slow code in any language.
> It'd be interesting to think how one could encode performance characteristics into equations.
I've seen the concept of encoding performance in types played around with, but I can't find actual work (if any) that's been done on it.
Yes, but Haskell makes that exceptionally easy.
Most of the Lisp hackers are usually knowledgeable about analysis of algorithm complexity.
Alan Perlis comment talks about inefficiency of Lisp programs due to a lot of (meta) abstraction and indirect mapping of abstract software to hardware.
You profile, and then you look at the suspicious parts.