Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: tutorials on space complexity? (Heinrich Apfelmus)
----------------------------------------------------------------------
Message: 1
Date: Tue, 10 Jun 2014 11:20:48 +0200
From: Heinrich Apfelmus <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] tutorials on space complexity?
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8; format=flowed
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
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 72, Issue 10
*****************************************
