Thanks for the links. The guidance on your blog post is exactly the kind of analysis I was looking for. Dimitri Em 10/06/14 06:20, Heinrich Apfelmus escreveu:
Dimitri DeFigueiredo wrote:
Are there any good tutorials on understanding space complexity for haskell programs?
My current approach of "waiting for it to crash" by being out of memory, doesn't really seem like good engineering practice. However, I have not found a source that gives me any proactive insight into what should be avoided. Most of what I have read only helps to solve the problem "after the fact". How do we design programs that avoid those problems from the beginning? Any pointers?
Lazy evaluation makes it difficult to reason about space usage -- it's not compositional anymore. However, I have found the following technique, dubbed "space invariants", to be very helpful:
http://apfelmus.nfshost.com/blog/2013/08/21-space-invariants.html
The main idea is that because it is impossible to trace lazy evaluation in detail, we have to use invariants. In particular, we can attach bounds on space usage to semantic meaning. Example:
"If this container with 5 elements is in WHNF, then it will use only as much space as the 5 elements."
(This invariant seems banal, but the point is that lazy evaluation does not preserve it.)
(WHNF means "weak head normal form", i.e. the expression has been evaluated to the outermost constructor.)
Best regards, Heinrich Apfelmus
-- http://apfelmus.nfshost.com
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners