[Haskell-beginners] State Monad in constant space?

[Harald Hanche-Olsen]

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.drautzburg at web.de(mailto:martin.drautzburg at 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?