Bug in Control.Monad.State

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
18 messages Options
Reply | Threaded
Open this post in threaded view
|

Bug in Control.Monad.State

Yitzchak Gale
In the following thread, I reported a problem I
was having with programs diverging when they use
infinite lists with StateT:

http://www.haskell.org//pipermail/haskell-cafe/2005-November/012253.html

Roberto Zunino and Wolfgang Jeltsch pointed out
that this is a bug in Control.Monad.State: (>>=)
is lazy in State, but strict in StateT.

The source of the problem is that the pattern
match in the definition of (>>=) is inside a let
expression in State - so it is lazy - but inside a
do expression inside StateT - so it strict.

Roberto suggests a one-byte patch to fix this
problem: add '~' to make the pattern match in
StateT irrefutable.

(Note that this has already been done for the
MonadFix instance of StateT.)

The same fix should be applied to evalStateT and
execStateT. They are also stricter than their
non-transformer counterparts, for the same reason.

-Yitz
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bug in Control.Monad.State

Iavor Diatchki
Hello,
It is not clear to me what is the right thing to do here (although I
agree that the transformer and the monad should be consistent).  In
'monadLib' at first I was very careful to make things as lazy as
possible, but then I noticed that this was a source of memory leaks,
that a user of the library could not really avoid.  So now I have
started making things stricter, not  in the state itself, but rather
the pair (result,state).  One always has to watch out for mfix, of
course, but things appear to be working at the moment.
-Iavor

On 11/21/05, Yitzchak Gale <[hidden email]> wrote:

> In the following thread, I reported a problem I
> was having with programs diverging when they use
> infinite lists with StateT:
>
> http://www.haskell.org//pipermail/haskell-cafe/2005-November/012253.html
>
> Roberto Zunino and Wolfgang Jeltsch pointed out
> that this is a bug in Control.Monad.State: (>>=)
> is lazy in State, but strict in StateT.
>
> The source of the problem is that the pattern
> match in the definition of (>>=) is inside a let
> expression in State - so it is lazy - but inside a
> do expression inside StateT - so it strict.
>
> Roberto suggests a one-byte patch to fix this
> problem: add '~' to make the pattern match in
> StateT irrefutable.
>
> (Note that this has already been done for the
> MonadFix instance of StateT.)
>
> The same fix should be applied to evalStateT and
> execStateT. They are also stricter than their
> non-transformer counterparts, for the same reason.
>
> -Yitz
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/libraries
>
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bug in Control.Monad.State

Yitzchak Gale
Hi Iavor,

> It is not clear to me what is the right thing to do here (although I
> agree that the transformer and the monad should be consistent).  In
> 'monadLib' at first I was very careful to make things as lazy as
> possible, but then I noticed that this was a source of memory leaks,
> that a user of the library could not really avoid.  So now I have
> started making things stricter,

Lack of laziness is also a serious problem that a
user cannot avoid. In my case, I have to
completely rewrite StateT, otherwise it is totally
unusable.  This is definitely a bug.

If you make State strict, I am sure it would break
many existing programs. (It would certainly break
many of mine.) I doubt that very much existing
code is relying on the accidental strictness in
StateT.

Strictness is a problem throughout the Haskell
libraries.  There was a recent discussion about
Data.Map, for example.  Right now, there seems to
be a need for at least two different versions of
every single container and monad in the library,
depending on strictness. It would be great if
someone could come up with a nicer and more
general approach.

(And if not - it would be nice of all of those
different versions would be added already.)

If we are forced to choose one or the other, I
would definitely vote for the lazy
version. Otherwise, what have we accomplished by
using Haskell?

Regards,
Yitz
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bug in Control.Monad.State

Udo Stenzel
Yitzchak Gale wrote:
> Lack of laziness is also a serious problem that a
> user cannot avoid. In my case, I have to
> completely rewrite StateT, otherwise it is totally
> unusable.  This is definitely a bug.

I disagree.  If an operation is lazy, there is absolutely nothing you as
a user can to to change that.  I've been bitten by that more than once.
If an operation is too strict (which I have yet to encounter), you can
always wrap the offending data in another constructor.


Udo.
--
I'm not prejudiced, I hate everyone equally.

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries

signature.asc (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Bug in Control.Monad.State

Iavor Diatchki
Hello,
Just to clarify, I wasn't suggesting that the the monad is strict in
the state component, but rather that it is strict in the pair
containing the result and the state.  This is a fine but important
distinction. I doubt it will break many programs, because the API to
the state monad always creates well formed pairs, even something like
'mfix return' is OK.
-Iavor


On 11/22/05, Udo Stenzel <[hidden email]> wrote:

> Yitzchak Gale wrote:
> > Lack of laziness is also a serious problem that a
> > user cannot avoid. In my case, I have to
> > completely rewrite StateT, otherwise it is totally
> > unusable.  This is definitely a bug.
>
> I disagree.  If an operation is lazy, there is absolutely nothing you as
> a user can to to change that.  I've been bitten by that more than once.
> If an operation is too strict (which I have yet to encounter), you can
> always wrap the offending data in another constructor.
>
>
> Udo.
> --
> I'm not prejudiced, I hate everyone equally.
>
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.1 (GNU/Linux)
>
> iD8DBQFDgyPyc1ZCC9bsOpURApYGAKCWQGLinm2r2ex0aQS+t1bE9+wHDACZAWpI
> cozKJqXa1qGzTlUHsy1uHIw=
> =7qbK
> -----END PGP SIGNATURE-----
>
>
>
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bug in Control.Monad.State

Josef Svenningsson
In reply to this post by Yitzchak Gale
Yitzchak,

I think you raise some very relevant questions about the design of Haskell libraries and how to deal with strictness/laziness. In my experience very few Haskell programmers have a feel for the strictness/laziness of a program. Even seasoned Haskell programmers have a hard time with this. Therefore I think that often the strictness/laziness of a function can be accidental rather than well thought through, even in libraries. However, this makes it even more important to think these issues through when designing a Haskell library. It's an issue which hasn't got by far the attention that it should have recieved.

About your request regarding the state monad. I think it is the wrong thing to make >>= strict. Experience tells us that most programmers program as if >>= were strict and the lazy version usually gives problems. That is why, for instance, the ST monad is strict by default. The gist of the problem is that when you make >>= lazy it does not perform a tail call anymore. This means that everytime you run >>= some piece of memory will be allocated. As an example, consider a server of some sort with an inner loop using a state monad. Making >>= lazy will mean that the server will inevitably run out of memory. But I very much agree with you that the library should provide a lazy state monad for those moments when the programmer knows what he is doing and he really wants laziness.

Incidentally I started working on a new monad library some time ago. The library was designed with the explicit goal of giving the programmer options about the strictness of functions and data structures while at the same time being convenient to use. I think I managaged pretty well to accomodate those goals. However, I never got around to finish it. Some day perhaps....

All the best,

/Josef

On 11/22/05, Yitzchak Gale <[hidden email]> wrote:
Hi Iavor,

> It is not clear to me what is the right thing to do here (although I
> agree that the transformer and the monad should be consistent).  In
> 'monadLib' at first I was very careful to make things as lazy as
> possible, but then I noticed that this was a source of memory leaks,
> that a user of the library could not really avoid.  So now I have
> started making things stricter,

Lack of laziness is also a serious problem that a
user cannot avoid. In my case, I have to
completely rewrite StateT, otherwise it is totally
unusable.  This is definitely a bug.

If you make State strict, I am sure it would break
many existing programs. (It would certainly break
many of mine.) I doubt that very much existing
code is relying on the accidental strictness in
StateT.

Strictness is a problem throughout the Haskell
libraries.  There was a recent discussion about
Data.Map, for example.  Right now, there seems to
be a need for at least two different versions of
every single container and monad in the library,
depending on strictness. It would be great if
someone could come up with a nicer and more
general approach.

(And if not - it would be nice of all of those
different versions would be added already.)

If we are forced to choose one or the other, I
would definitely vote for the lazy
version. Otherwise, what have we accomplished by
using Haskell?

Regards,
Yitz
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bug in Control.Monad.State

Yitzchak Gale
In reply to this post by Udo Stenzel
Hi Udo,

> > Lack of laziness is also a serious problem
> > that a user cannot avoid. In my case, I have
> > to completely rewrite StateT, otherwise it is
> > totally unusable.  This is definitely a bug.

> I disagree. If an operation is lazy, there is
> absolutely nothing you as a user can to to
> change that.

Right. Well, you can rewrite the library, or you
can restructure your entire app, but neither of
those are very good options.

> If an operation is too strict...  you can always
> wrap the offending data in another constructor.

I have seen this claim several times, but I am
not yet convinced.

In my case, the unwanted strictness is coming from
the bind method of a monad from the standard
libraries. I don't see how to get rid of that
strictness by wrapping something in a constructor.

And even when it is possible to reduce strictness
by wrapping something - it means changing the
interface of existing functions. In a large
application, that could be a major disaster.

Here is an example. How would you fix this by
wrapping something in a constructor?  No
restructuring is allowed (this is one function in
a large application, so changing the interface of
any function could have major consequences), and
no rewriting libraries is allowed.

You need to construct a random list of items. you
do not know in advance how many I will need; that
is determined by a stateful calculation as you
construct the items. Here is the function; it
diverges, unless you rewrite StateT with
strictness removed:

createItems :: RandomGen g => State g [Item]
createItems =
  liftM catMaybes $ runListT $
  flip evalStateT initialState $ runMaybeT $
  do
    item <- liftRandom $ repeatM randomItem
    updateState item
    needMoreItems >>= guard
    return item
  where
    liftRandom = lift . lift . lift

Regards,
Yitz
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bug in Control.Monad.State

Yitzchak Gale
In reply to this post by Iavor Diatchki
Hi Iavor,

> Just to clarify, I wasn't suggesting that the
> the monad is strict in the state component, but
> rather that it is strict in the pair containing
> the result and the state.

Does this help in the "createItems" examples I
sent to Udo in the previous post?

Thanks,
Yitz

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bug in Control.Monad.State

Yitzchak Gale
In reply to this post by Josef Svenningsson
Hi Josef,

You wrote:
> ...Experience tells us that most programmers
> program as if >>= were strict and the lazy
> version usually gives problems. That is why, for
> instance, the ST monad is strict by default.

That is only true for IO. And for ST, which is
really just IO restricted to IORefs. In these
unusual monads that interact with the Real World,
one expects strictness.

The monads of the mtl library - and most others -
are meant for pure programs that lend themselves
to monadic paradigms. Here one expects laziness,
as usual in Haskell.

Many monad beginners do seem to make the mistake
you are referring to. The reason is that they
start by using only the IO monad before learning
much else about what monads are for. I think that
will improve once we begin to see more
introductions to Haskell geared to practical
programmers.

> As an example, consider a server of some sort
> with an inner loop using a state monad. Making
> >>= lazy will mean that the server will
> inevitably run out of memory.

Servers interact with the Real World, so you would
use IO and ST. But you are right, it would be
great to have special strict versions of various
monads (and containers like Data.Map) for these
situations.

Regards,
Yitz
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bug in Control.Monad.State

Iavor Diatchki
In reply to this post by Yitzchak Gale
Hello,
I did not understand the example you posted, as it contains functions
that are not defined, but here is something you can do (this is using
monadLib, but something like that should probably work with the
libraries distributed with GHC).  Let me know if this helps.
-Iavor

import Monad.StateT
import Monad.Id
import Random

type M        = StateT (StdGen,[Int]) Id

randomItem   :: M ()
randomItem    = do (g,xs) <- peek
                   let (x,g') = random g
                   poke_ (g',mod x 5 : xs)

needMoreItems :: M Bool
needMoreItems = do (_,xs) <- peek
                   return (sum xs < 50)

whileM p b    = do x <- p
                   if x then b >> whileM p b else return ()

test          = do g <- newStdGen
                   print $ runId $ evalState (g,[])
                                 $ do whileM needMoreItems randomItem
                                      (_,xs) <- peek
                                      return xs


On 11/22/05, Yitzchak Gale <[hidden email]> wrote:

> Hi Iavor,
>
> > Just to clarify, I wasn't suggesting that the
> > the monad is strict in the state component, but
> > rather that it is strict in the pair containing
> > the result and the state.
>
> Does this help in the "createItems" examples I
> sent to Udo in the previous post?
>
> Thanks,
> Yitz
>
>
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bug in Control.Monad.State

Iavor Diatchki
In reply to this post by Yitzchak Gale
Hello,
I did not understand the example you posted, as it contains functions
that are not defined, but here is something you can do (this is using
monadLib, but something like that should probably work with the
libraries distributed with GHC).  Letme know if this helps.
-Iavor

import Monad.StateT
import Monad.Id
import Random

type M        = StateT (StdGen,[Int]) Id

randomItem   :: M ()
randomItem    = do (g,xs) <- peek
                   let (x,g') = random g
                   poke_ (g',mod x 5 : xs)

needMoreItems :: M Bool
needMoreItems = do (_,xs) <- peek
                   return (sum xs < 50)

whileM p b    = do x <- p
                   if x then b >> whileM p b else return ()

test          = do g <- newStdGen
                   print $ runId $ evalState (g,[])
                                 $ do whileM needMoreItems randomItem
                                      (_,xs) <- peek
                                      return xs


On 11/22/05, Yitzchak Gale <[hidden email]> wrote:

> Hi Iavor,
>
> > Just to clarify, I wasn't suggesting that the
> > the monad is strict in the state component, but
> > rather that it is strict in the pair containing
> > the result and the state.
>
> Does this help in the "createItems" examples I
> sent to Udo in the previous post?
>
> Thanks,
> Yitz
>
>
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bug in Control.Monad.State

Yitzchak Gale
> ...I did not understand the example you posted,
> as it contains functions that are not defined...

Sorry. I actually think you understood it quite
well, from what you wrote in reply. But OK, I will
put in some more annotation below.

> but here is something you can do (...using
> monadLib...).  Letme know if this helps.

Well, I like using infinite lists - where a
sequence is completely decoupled from its end
conditions - as opposed to while-loop-like
constructs. And other such lazy paradigms when
appropriate. And I also like using monads when
they make my code more clear - which is usually.

And I like using these things together when they
happen to coincide. I gave Udo an example of a
common kind of situation in which that happens.

You wrote that you introduced some limited kind of
strictness in your state monad. My question was:
Can I still use infinite lists and state monads
together in monadLib?  I think your answer is
"No." Am I correct?

Regards,
Yitz

Iavor's code:

> import Monad.StateT
> import Monad.Id
> import Random
>
> type M        = StateT (StdGen,[Int]) Id
>
> randomItem   :: M ()
> randomItem    = do (g,xs) <- peek
>                    let (x,g') = random g
>                    poke_ (g',mod x 5 : xs)
>
> needMoreItems :: M Bool
> needMoreItems = do (_,xs) <- peek
>                    return (sum xs < 50)
>
> whileM p b    = do x <- p
>                    if x then b >> whileM p b else return ()
>
> test          = do g <- newStdGen
>                    print $ runId $ evalState (g,[])
>                                  $ do whileM needMoreItems randomItem
>                                       (_,xs) <- peek
>                                       return xs

My code (that I wrote to Udo), with additional annotation:

import System.Random
import Control.Monad.State

createItems :: RandomGen g => State g [Item]
createItems =
  liftM catMaybes $ runListT $
  flip evalStateT initialState $ runMaybeT $
  do
    item <- liftRandom $ repeatM randomItem
    updateState item
    needMoreItems >>= guard
    return item
  where
    liftRandom = lift . lift . lift

-- The type of the items we need to create.
type Item = Int

-- Create one random item.
randomItem :: RandomGen g => State g Item
randomItem = State $ randomR (1, 5)

-- The type of the state we need to keep while
-- computing whether we have enough items yet.
type MyState = Int

-- The initial state while computing whether we
-- have enough items yet.
initialState :: MyState
initialState = 0

-- Update the state after creating an Item.
updateState :: MonadState MyState m => Item -> m ()
updateState = modify . (+)

--Do we need any more items?
needMoreItems :: MonadState MyState m => m Bool
needMoreItems = gets (< 50)

-- repeatM is still missing from Control.Monad.
-- I hope they will put it in soon.
repeatM :: Monad m => m a -> m [a]
repeatM = sequence . repeat

-- MaybeT is still missing from mtl.
-- I hope they will put it in soon.
newtype MaybeT m a = MaybeT {runMaybeT :: m (Maybe a)}
instance Monad m => Monad (MaybeT m) where ...
instance Monad m => MonadPlus (MaybeT m) where ...
instance MonadState s m => MonadState s (MaybeT m) where ...
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bug in Control.Monad.State

Udo Stenzel
In reply to this post by Yitzchak Gale
Hello Yitzchak,
 

> > If an operation is too strict...  you can always
> > wrap the offending data in another constructor.
>
> I have seen this claim several times, but I am
> not yet convinced.
>
> In my case, the unwanted strictness is coming from
> the bind method of a monad from the standard
> libraries. I don't see how to get rid of that
> strictness by wrapping something in a constructor.
as Iavor already pointed out, theres the fine difference between being
string in some implementation detail (the pair of state and result) or
in the state itself, which I missed.

I was thinking of the state component, and I maintain that it should be
strict.  Rationale: if the state is some primitive type, you want it
strict anyway.  If it isn't, the strictness doesn't cost much anyway.
If it's still wrong, wrapping in a constructor helps.

Your problem however is the strict match against a pair you don't even
know is there.  Indeed, a strict match against a single constructor
datatype is probably always pointless.  So it's really a bug in the
library, after all.

 
> Here is an example. How would you fix this by
> wrapping something in a constructor?

You can't, since you don't have access to the offending pair.
 

> createItems :: RandomGen g => State g [Item]
> createItems =
>   liftM catMaybes $ runListT $
>   flip evalStateT initialState $ runMaybeT $
>   do
>     item <- liftRandom $ repeatM randomItem
>     updateState item
>     needMoreItems >>= guard
>     return item
>   where
>     liftRandom = lift . lift . lift
...but this is probably broken anyway.  After (repeatM randomItem)
presumably the state (the RandomGen) is _|_, but the type of createItems
would suggest it is still usable.  I wouldn't do that.  Other than that
it's a bit hard to see what you're trying to accomplish here.


Udo.
--
"Gadgets are not necessarily an improvement, vide the succession:
Blackboard -> Overhead Projector -> PowerPoint"
        -- E. W. Dijkstra

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries

signature.asc (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

RE: Bug in Control.Monad.State

Simon Marlow
In reply to this post by Yitzchak Gale
Apologies for being a bit blunt, but can't this problem be solved by
introducing a LazyStateT in addition to StateT?  This follows the
pattern of ST (default is strict, we also have Control.Monad.ST.Lazy).

Cheers,
        Simon

On 23 November 2005 09:59, Udo Stenzel wrote:

> Hello Yitzchak,
>
>>> If an operation is too strict...  you can always
>>> wrap the offending data in another constructor.
>>
>> I have seen this claim several times, but I am
>> not yet convinced.
>>
>> In my case, the unwanted strictness is coming from
>> the bind method of a monad from the standard
>> libraries. I don't see how to get rid of that
>> strictness by wrapping something in a constructor.
>
> as Iavor already pointed out, theres the fine difference between being
> string in some implementation detail (the pair of state and result) or
> in the state itself, which I missed.
>
> I was thinking of the state component, and I maintain that it should
> be strict.  Rationale: if the state is some primitive type, you want
> it strict anyway.  If it isn't, the strictness doesn't cost much
> anyway. If it's still wrong, wrapping in a constructor helps.
>
> Your problem however is the strict match against a pair you don't even
> know is there.  Indeed, a strict match against a single constructor
> datatype is probably always pointless.  So it's really a bug in the
> library, after all.
>
>
>> Here is an example. How would you fix this by
>> wrapping something in a constructor?
>
> You can't, since you don't have access to the offending pair.
>
>> createItems :: RandomGen g => State g [Item]
>> createItems =
>>   liftM catMaybes $ runListT $
>>   flip evalStateT initialState $ runMaybeT $
>>   do
>>     item <- liftRandom $ repeatM randomItem
>>     updateState item
>>     needMoreItems >>= guard
>>     return item
>>   where
>>     liftRandom = lift . lift . lift
>
> ...but this is probably broken anyway.  After (repeatM randomItem)
> presumably the state (the RandomGen) is _|_, but the type of
> createItems would suggest it is still usable.  I wouldn't do that.
> Other than that it's a bit hard to see what you're trying to
> accomplish here.
>
>
> Udo.

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bug in Control.Monad.State

Yitzchak Gale
On Wed, Nov 23, 2005 at 10:47:02AM -0000, Simon Marlow wrote:
> Apologies for being a bit blunt, but can't this
> problem be solved by introducing a LazyStateT in
> addition to StateT?  This follows the pattern of
> ST (default is strict, we also have
> Control.Monad.ST.Lazy).

That would be great. Except that I would prefer
StrictState, with laziness the default. ST is from
the IO family of monads, so one expects
strictness. MTL monads are usually pure, so the
default should be laziness like everywhere else in
Haskell.

Many of the programs I have written in the past
few years would break if State were to become
strict.

But in any case, there is still a bug to
fix. State and StateT are currently straddling
both sides of the fence; State is lazy, and StateT
is strict.

Regards,
Yitz
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bug in Control.Monad.State

Yitzchak Gale
In reply to this post by Udo Stenzel
On Wed, Nov 23, 2005 at 10:58:55AM +0100, Udo Stenzel wrote:
> I was thinking of the state component, and I maintain that it should be
> strict.  Rationale: if the state is some primitive type, you want it
> strict anyway.  If it isn't, the strictness doesn't cost much anyway.
> If it's still wrong, wrapping in a constructor helps.

I can see your point. But we have to be careful;
this kind of thing adds complexity to the
language, making Haskell harder to learn and
programs harder to understand.

My intuition tells me:

- Things directly related to IO are strict. E.g.,
  IO, ST, file operations, threads, etc.

- Things marked explicitly as being strict are
  strict.  E.g., seq, $!, StrictState,
  Data.Map.StrictMap, etc.

- Everything else is lazy - because Haskell is lazy!

I think that is pretty much the case today.

That may not always be optimal, as you point out.
But it sure makes it much easier for me do work
in Haskell on a day to day basis.

Regards,
Yitz
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bug in Control.Monad.State

Yitzchak Gale
In reply to this post by Udo Stenzel
Hi Udo,

I am posting this response here on the libraries list,
because it is relevant to the discussion about whether
State should be lazy or strict by default.

I am also cross-posting to the haskell list, because
I think the topic may be of more general interest.

I wrote:

> > createItems :: RandomGen g => State g [Item]
> > createItems =
> >   liftM catMaybes $ runListT $
> >   flip evalStateT initialState $ runMaybeT $
> >   do
> >     item <- liftRandom $ repeatM randomItem
> >     updateState item
> >     needMoreItems >>= guard
> >     return item
> >   where
> >     liftRandom = lift . lift . lift

Udo Stenzel wrote:
> ...but this is probably broken anyway.  After
> (repeatM randomItem) presumably the state (the
> RandomGen) is _|_, but the type of createItems
> would suggest it is still usable.

No, it works. MaybeT tells ListT when to stop its
iteration. After that, the RandomGen can be used
again elsewhere.

>  I wouldn't do that.  Other than that it's a bit
> hard to see what you're trying to accomplish
> here.

Lazy monads are an important programming paradigm
in practice.

Laziness helps to completely decouple the various
ingredients of the algorithm from each other.
This helps in debugging, and in dividing tasks
among different development teams.

The monadic approach helps makes refactoring easy
(a common complaint against Haskell). For example,
it would be trivial to add exception handling,
or logging.

The algorithm is clearly specified as an iteration
of a series of steps, the way most people would
naturally think of it. Yet the calculation is
completely pure. So a compiler is not required to
follow the steps literally. It can split the
calculation across different threads, processors,
http connections, etc., if it is smart enough.

This is the way industrial software development
should be done. It is clearly far better than
imperative OO.

Regards,
Yitz
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Bug in Control.Monad.State

Iavor Diatchki
In reply to this post by Yitzchak Gale
Hello,
I am still confused, sorry :-) It appears that the code has a type error:
repeatM randomItem :: State g [Int]
so, isn't 'item' of type '[Int]'.  On the other hand, 'updateState' is
expecting an 'Int' as an argument...
-Iavor

> createItems :: RandomGen g => State g [Item]
> createItems =
>   liftM catMaybes $ runListT $
>   flip evalStateT initialState $ runMaybeT $
>   do
>     item <- liftRandom $ repeatM randomItem
>     updateState item
>     needMoreItems >>= guard
>     return item
>   where
>     liftRandom = lift . lift . lift
>
> -- Create one random item.
> randomItem :: RandomGen g => State g Item
> randomItem = State $ randomR (1, 5)
>
> -- repeatM is still missing from Control.Monad.
> -- I hope they will put it in soon.
> repeatM :: Monad m => m a -> m [a]
> repeatM = sequence . repeat
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries