[Haskell-beginners] tutorials on space complexity?

[Dimitri DeFigueiredo]

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners