News for hackers. Stuff that matters.
Re:Turn O(n^2) reverse into O(n) by velis_vel on Monday December 16, 2013 @04:47AM (#6913745)
I don't think this was an 'oh my god we're trying to track down why cabal update is so slow and we just can't find it' issue like you make it out to be.

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.

Re:Turn O(n^2) reverse into O(n) by zvrba on Monday December 16, 2013 @05:58AM (#6914001)
I didn't try to imply that it was difficult to find the performance problem. It's an observation on something else: Haskell is often mentioned for its equational reasoning. I find it interesting that correct equational reasoning in this case lead to a correct program, but one with absymal performance.

It'd be interesting to think how one could encode performance characteristics into equations.

Re:Turn O(n^2) reverse into O(n) by Peaker on Monday December 16, 2013 @12:06PM (#6916067)
I think having simple and direct denotational semantics necessarily means having relatively complex, indirect operational semantics (e.g: Haskell). Having a simple and direct operational semantics necessarily means having complex and indirect denotational semantics (e.g: C).

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.

Re:Turn O(n^2) reverse into O(n) by zvrba on Tuesday December 17, 2013 @02:28AM (#6919987)
Why do you think that there must be a tradeoff between simplicity of denotational and operational semantics?
Re:Turn O(n^2) reverse into O(n) by Peaker on Tuesday December 17, 2013 @08:03AM (#6920858)
Because operational semantics (of contemporary computers, at least) are very different from a simple denotational semantics.

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

Re:Turn O(n^2) reverse into O(n) by jjaredsimpson on Monday December 16, 2013 @06:58AM (#6914209)
Its known that postpending to a linked list is slow. It's just a property of the data type.
Re:Turn O(n^2) reverse into O(n) by velis_vel on Monday December 16, 2013 @12:12PM (#6916121)
> I find it interesting that correct equational reasoning in this case lead to a correct program, but one with absymal performance.

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.

Re:Turn O(n^2) reverse into O(n) by eru on Monday December 16, 2013 @10:32PM (#6919442)
> You can always write correct but slow code in any language.

Yes, but Haskell makes that exceptionally easy.