Send Beginners mailing list submissions to
beginners@haskell.org
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: State Monad in constant space? (Harald Hanche-Olsen)
2. Re: State Monad in constant space? (David McBride)
----------------------------------------------------------------------
Message: 1
Date: Tue, 14 Jun 2016 14:47:08 +0000
From: Harald Hanche-Olsen <han...@math.ntnu.no>
To: martin <martin.drautzb...@web.de>, "The Haskell-Beginners Mailing
List - Discussion of primarily beginner-level topics related to
Haskell" <beginners@haskell.org>
Subject: Re: [Haskell-beginners] State Monad in constant space?
Message-ID: <etpan.576018f9.2b3ad90d.d...@math.ntnu.no>
Content-Type: text/plain; charset="utf-8"
Being an absolute beginner myself, I should probably refrain from trying to
answer this one, but since no one else did, I?ll give it a shot:
I assume it all comes down to laziness. The gargantuan expression will not be
built all at once, but rather the beginning of it is built and evaluated. The
result of evaluating the leftmost part will (hopefully) be simpler than the
expression that defined it! In any case, that expression is now safely
discarded, a bit more of the expression is built, and the evaluation can
proceed. The principle shouldn?t be all that different from any tail recursive
function application, really.
? Harald
On 12 June 2016 at 23:11:32, martin
(martin.drautzb...@web.de(mailto:martin.drautzb...@web.de)) wrote:
> Hello all,
>
> the State Monad wraps around a computation s -> (s,a). Inside a do block I am
> actually assembling such a computation.
> Now when I do this many times, i.e. in a recursice call, I am builing a huge
> expression
>
> m a >>= (\a -> mb) >>= (\b -> mc) ...
>
> The result of this expression is a function s -> (s,a). But I cannot see how
> the space for this expression can be
> reclaimed, and how it could ever run in constant space. Once I call runState
> and I provide an initial s, I have some
> hope, but before?
>
> How is this supposed to work? How do I avoid allocating space for this huge
> expression?
------------------------------
Message: 2
Date: Tue, 14 Jun 2016 11:27:08 -0400
From: David McBride <toa...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] State Monad in constant space?
Message-ID:
<CAN+Tr40+W6jh=TNT=6LPWv05t0uzCkPf=gaggxjiyp3xblq...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Remember that StateT (and by extension, State) is just a newtype wrapper.
Newtypes have no runtime cost. In this case it simply contains a
function. Constructing an expression full of binds against StateT before
supplying an argument via runStateT is no different than combining several
functions and supplying their argument later.
As far as memory usage is concerned, there is one caveat. The state
variable that is returned after every bind can build up thunks if it is
altered but not fully evaluated in any given step. This could lead to a
memory link as operations are tacked onto the state variable you supplied.
If you use Control.Monad.State.Strict, that variable will be evaluated
whether you use it or not, preventing laziness from building up thunks.
On Sun, Jun 12, 2016 at 5:11 PM, martin <martin.drautzb...@web.de> wrote:
> Hello all,
>
> the State Monad wraps around a computation s -> (s,a). Inside a do block I
> am actually assembling such a computation.
> Now when I do this many times, i.e. in a recursice call, I am builing a
> huge expression
>
> m a >>= (\a -> mb) >>= (\b -> mc) ...
>
> The result of this expression is a function s -> (s,a). But I cannot see
> how the space for this expression can be
> reclaimed, and how it could ever run in constant space. Once I call
> runState and I provide an initial s, I have some
> hope, but before?
>
> How is this supposed to work? How do I avoid allocating space for this
> huge expression?
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20160614/f0499655/attachment-0001.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 96, Issue 11
*****************************************
