[Haskell-beginners] tutorials on space complexity?

[Heinrich Apfelmus]

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