[Haskell-cafe] Stacking State on State.....

[Phil]

Thanks again - one quick question about lazy pattern matching below!


On 01/03/2009 23:56, "Daniel Fischer" <daniel.is.fischer at web.de> wrote:


> 
> No, it's not that strict. If it were, we wouldn't need the bang on newStockSum
> (but lots of applications needing some laziness would break).
> 
> The Monad instance in Control.Monad.State.Strict is
> 
> instance (Monad m) => Monad (StateT s m) where
>     return a = StateT $ \s -> return (a, s)
>     m >>= k  = StateT $ \s -> do
>         (a, s') <- runStateT m s
>         runStateT (k a) s'
>     fail str = StateT $ \_ -> fail str
> 
> (In the lazy instance, the second line of the >>= implementation is
> ~(a,s') <- runStateT m s)
> 
> The state will only be evaluated if "runStateT m" resp. "runStateT (k a)"
> require it. However, it is truly separated from the return value a, which is
> not the case in the lazy implementation.
> The state is an expression of past states in both implementations, the
> expression is just much more complicated for the lazy.
>> 

I think I get this - so what the lazy monad is doing is delaying the
evaluation of the *pattern* (a,s') until it is absolutely required.
This means that each new (value,state) is just passed around as a thunk and
not even evaluated to the point where a pair is constructed - it's just a
blob, and could be anything as far as haskell is concerned.
It follows that each new state cannot evaluated even if we make newStockSum
strict as (by adding a bang) because the state tuple newStockSum is wrapped
in is completely unevaluated - so even if newStockSum is evaluated INSIDE
this blob, haskell will still keep the whole chain.
Only when we actually print the result is each state required and then each
pair is constructed and incremented as described by my transformer.  This
means that every tuple is held as a blob in memory right until the end of
the full simulation.
Now with the strict version each time a new state tuple is created, to check
that the result of running the state is at least of the form (thunk,thunk).
It won't actually see much improvement just doing this because even though
you're constructing pairs on-the-fly we are still treating each state in a
lazy fashion.  Thus right at the end we still have huge memory bloat, and
although we will not do all our pair construction in one go we will still
value each state after ALL states have been created - performance
improvement is therefore marginal, and I'd expect memory usage to be more or
less the same as (thunk,thunk) and thunk must take up the same memory.

So, we stick a bang on the state.  This forces each state to evaluated at
simulation time.  This allows the garbage collector to throw away previous
states as the present state is no longer a composite of previous states AND
each state has been constructed inside it's pair - giving it Normal form.

Assuming that is corrected, I think I've cracked it.

One last question if we bang a variable i.e. !x = blah blah, can we assume
that x will then ALWAYS be in Normal form or does it only evaluate to a
given depth, giving us a stricter WHNF variable, but not necessarily
absolutely valued?