[Haskell-cafe] State monad strictness - how?
Yitzchak Gale
gale at sefer.org
Thu Jan 11 07:59:26 EST 2007
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.
>>> 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.
>> The same challenge exists in many of the Data.*
>> libraries. I think this is very important.
I am now a bit more optimistic. Has anyone looked
through them?
> 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.
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.
Regards,
Yitz
More information about the Haskell-Cafe
mailing list