News for hackers. Stuff that matters.
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.