[Haskell-beginners] tutorials on space complexity?
apfelmus at quantentunnel.de
Tue Jun 10 09:20:48 UTC 2014
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:
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.)
More information about the Beginners