[Haskell-cafe] State monad strictness - how?

[Josef Svenningsson]

On 1/11/07, Yitzchak Gale <gale at sefer.org> wrote:
> Josef Svenningsson wrote:
> >>> Take the state monad for example. Should it be
> >>> strict or lazy in the state that it carries
> >>> around? What about the value component?
> >>> ...both strict and lazy variants are useful.
>
> I wrote:
> >> Are those really needed?
>
> > ...it wouldn't be very convenient, would it?
> > Sometimes I find that I want strict state by
> > default and then I don't want to sprinkle my
> > code with seqs.
>
> I don't think that is so inconvenient. Why do we
> need to define getStrict, putStrict, getsStrict,
> etc., when it is perhaps even more clear to write
> get $!, put $!., (gets . ($!)), etc.?.
>
> The same goes for Iavor's monad library.
>
Indeed. I'm embarrassed that I've never realized this before. I
suppose I though the tuple solution was so elegant that I never
realized there was a simpler solution at hand.

> >>> Now, the challenge here is to design a library
> >>> which doesn't explode in size from all the
> >>> various possibilities for strictness or
> >>> laziness.
>
> I am now pretty convinced that the only thing we
> need is two versions of each monad, varying only
> the strictness of >>=.
>
> Then, of course, we will need runFoo for each, and
> evalFoo and execFoo for each state monad.
>
> And adaptors that allow you to run a lazy
> calculation inside a strict one and vice-versa. So
> we need an asStrict function and an asLazy
> function for each lazy/strict pair of monads.
>
> I think that is all we need. Not too bad.
>
> I am very impressed that we get most of that
> almost for free in Iavor's library.
>
Yes, it seems quite feasible.

> > http://www.cs.chalmers.se/~josefs/monadlib/
> > ...instantiating this with different pair types
> > with different strictness properties will give
> > us total control over strictness for state and
> > value.
>
> Hmm. Your current implementation doesn't seem to
> do it that way. You use tuples for both the lazy
> version and the strict version, and each defines
> its own Monad instance for all Pair types. So it
> is impossible to use both in the same module, even
> with hiding.
>
The way I enable laziness in a strict monad and vice versa is to use a
non-standard bind operator, strictBind or lazyBind. But that's not
really scalable. The whole architecture that I used in my library
isn't really all that good. The reason I came up with it was to solve
a completely different problem which doesn't really apply to this
library anyway. The library design you outline above is indeed the way
to go.

> I tried to work on this a little. I defined a
> strict Pair type and tried to find a single Monad
> instance that will give the right strictness for
> both if you just vary between lazy and strict
> pairs.
>
> We need that both of the following converge
> in constant stack space:
>
> take 100 $ evalState (repeatM $ modify (+1)) 0
> execStateStrict (replicateM_ 100000 $ modify (+1)) 0
>
> (You can verify that this is true if you use the
> standard evalState, and replace execStateStrict
> with runIdentity . execStateT.)
>
> I was unable to hit upon the right combination of
> seqs in the Monad instance. Is it really possible?
>
> Of course, you could use a newtype of tuples and
> define separate Monad instances. But then we are
> not gaining anything over just defining the lazy
> and strict monads directly.
>
I'm not sure exactly what you're trying to achieve here. If the tuple
type you have is strict in both components then you're never going to
get these examples to work. However, if you choose the lazy state
monad and choose tuples carefully then both example can be made to
terminate. Here's an example:
ex1 = take 100 $ evalState
      ((repeatM $ modify (+1))::StateP StrictLeft Int [()])
      0
ex2 = execStateStrict
      ((replicateM_ 100000 $ modify (+1)) :: StateTP StrictLeft Int Identity ())
      0

The first example also terminates with the all lazy pair (,), the
importance is the laziness of the right component.

Cheers,

Josef