Proposal: Make StateT in mtl lazy
http://hackage.haskell.org/trac/ghc/ticket/1127 Deadline: 28 February 2007. I propose we make StateT lazy, as I suspect was the intention all along and as has been discussed (without reaching a conclusion) before. The patch is simply (in the definition of (>>=)): hunk ./Control/Monad/State.hs 195 - (a, s') <- runStateT m s + ~(a, s') <- runStateT m s Thanks Ian
I agree that the change improves the consistence of semantics. You should amend the proposal to also explain how to restore the previous strictness using 'seq'. And if StateT is to be fixed, then the same fix should be applied to WriterT, as shown in http://haskell.org/haskellwiki/New_monads/LazyWriterT And the same fix looks like it should be applied to RWST. ErrorT I believe is supposed to be Strict, so it can stop when a (Left _) is found. Ian Lynagh wrote:
http://hackage.haskell.org/trac/ghc/ticket/1127
Deadline: 28 February 2007.
I propose we make StateT lazy, as I suspect was the intention all along and as has been discussed (without reaching a conclusion) before.
The patch is simply (in the definition of (>>=)):
hunk ./Control/Monad/State.hs 195 - (a, s') <- runStateT m s + ~(a, s') <- runStateT m s
Thanks Ian
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
On Tue, Jan 30, 2007 at 05:07:18PM +0000, Chris Kuklewicz wrote:
I agree that the change improves the consistence of semantics.
You should amend the proposal to also explain how to restore the previous strictness using 'seq'.
I'm not sure what you mean?
And if StateT is to be fixed, then the same fix should be applied to WriterT, as shown in http://haskell.org/haskellwiki/New_monads/LazyWriterT
And the same fix looks like it should be applied to RWST.
ErrorT I believe is supposed to be Strict, so it can stop when a (Left _) is found.
Hmm, now I look closer there are a number of other places that look like they could benefit from a ~. I've attached a new patch and unified diff of them all to the proposal http://hackage.haskell.org/trac/ghc/ticket/1127 and changed the description to match its increased scope. The changes only affect transformers except for: listens :: (MonadWriter w m) => (w -> b) -> m a -> m (a, b) listens f m = do - (a, w) <- listen m + ~(a, w) <- listen m return (a, f w) in Control/Monad/Writer.hs Thanks Ian
igloo:
http://hackage.haskell.org/trac/ghc/ticket/1127
Deadline: 28 February 2007.
I propose we make StateT lazy, as I suspect was the intention all along and as has been discussed (without reaching a conclusion) before.
The patch is simply (in the definition of (>>=)):
hunk ./Control/Monad/State.hs 195 - (a, s') <- runStateT m s + ~(a, s') <- runStateT m s
Is it possible to provide a short example of the different behaviours you need or expect? -- Don
On Wed, Jan 31, 2007 at 11:22:54AM +1100, Donald Bruce Stewart wrote:
igloo:
http://hackage.haskell.org/trac/ghc/ticket/1127
Deadline: 28 February 2007.
I propose we make StateT lazy, as I suspect was the intention all along and as has been discussed (without reaching a conclusion) before.
The patch is simply (in the definition of (>>=)):
hunk ./Control/Monad/State.hs 195 - (a, s') <- runStateT m s + ~(a, s') <- runStateT m s
Is it possible to provide a short example of the different behaviours you need or expect?
The attached without the ~ gives: $ time ./p 1000000 Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize' to increase it. ./p 1000000 1.96s user 0.05s system 96% cpu 2.095 total whereas with the ~ you can pump up the argument as high as you like without any runtime or stack use worries: $ time ./p 1000000 'a' ./p 1000000 0.00s user 0.00s system 93% cpu 0.004 total $ time ./p 1000000000 'a' ./p 1000000000 0.00s user 0.00s system 101% cpu 0.004 total For a non-contrived example see the compression package in hackage. Thanks Ian
On Tue, Jan 30, 2007 at 04:58:48PM +0000, Ian Lynagh wrote:
I propose we make StateT lazy
SimonM writes:
I don't mind whether StateT itself is lazy or not, but I think we should have a strict version. In GHC the implementation should use unboxed tuples, like IO.
If we're going to have a strict StateT then it would make sense to have a strict State too. Control.Monad.State.Strict perhaps? (and likewise for the other mtl monads, where appropriate). Or perhaps go a bit further and have: Control.Monad.State.Class -- for the MonadState class Control.Monad.State.Lazy Control.Monad.State.Strict Control.Monad.State -- re-exports .Class and .Lazy There's perhaps an argument for splitting the package into mtl-classes, mtl-lazy and mtl-strict but I think that that would be overkill at this stage. There's going to be a lot of duplication between the lazy and strict (and GHC) variants, but short of some hideous CPP I don't think there's a nice solution. By "strict", do you mean this?: instance Monad (State s) where return a = State $ \s -> (a, s) m >>= k = State $ \s -> case runState m s of (a, s') -> runState (k a) $! s' 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 Thanks Ian
Hi
If we're going to have a strict StateT then it would make sense to have a strict State too. Control.Monad.State.Strict perhaps? (and likewise for the other mtl monads, where appropriate).
For foldl we have foldl and foldl'. Why not State and State' ? I'm not a particular fan of changing the imports to get different sets of behaviours... Thanks Nel
On Wed, Jan 31, 2007 at 04:06:07PM +0000, Neil Mitchell wrote:
If we're going to have a strict StateT then it would make sense to have a strict State too. Control.Monad.State.Strict perhaps? (and likewise for the other mtl monads, where appropriate).
For foldl we have foldl and foldl'.
Right, and I'd guess about a dozen other functions dotted around the core libraries.
Why not State and State' ? (refering to type names, not module names)
This would also presumably give us runState' evalState' ... runStateT' evalStateT' ... Existing examples of using .Strict/.Lazy modules are: Control.Monad.ST.Lazy Control.Monad.ST.Strict Data.STRef.Lazy Data.STRef.Strict Data.ByteString Data.ByteString.Lazy Has anyone else got an opinion as to which is preferable? Thanks Ian
Neil Mitchell wrote:
Hi
If we're going to have a strict StateT then it would make sense to have a strict State too. Control.Monad.State.Strict perhaps? (and likewise for the other mtl monads, where appropriate).
For foldl we have foldl and foldl'. Why not State and State' ? I'm not a particular fan of changing the imports to get different sets of behaviours...
So if you want (gasp!) strictness you have to pay the Prime Tax :-) I'm not keen on having a bias implied by the naming convention: State' suggests that this is a special/modified version of State, whereas I think both versions are equally useful. Using lazy when you wanted strict can result in a space leak, using strict when you wanted lazy can result in a stack overflow or a time leak. I don't mind so much a bias in the module names: e.g. Control.Monad.State could be the lazy version, Control.Monad.State.Strict the strict version, that's much less intrusive. Cheers, Simon
Simon Marlow wrote:
Neil Mitchell wrote:
Hi
If we're going to have a strict StateT then it would make sense to have a strict State too. Control.Monad.State.Strict perhaps? (and likewise for the other mtl monads, where appropriate).
For foldl we have foldl and foldl'. Why not State and State' ? I'm not a particular fan of changing the imports to get different sets of behaviours...
So if you want (gasp!) strictness you have to pay the Prime Tax :-)
I'm not keen on having a bias implied by the naming convention: State' suggests that this is a special/modified version of State, whereas I think both versions are equally useful. Using lazy when you wanted strict can result in a space leak, using strict when you wanted lazy can result in a stack overflow or a time leak.
I don't mind so much a bias in the module names: e.g. Control.Monad.State could be the lazy version, Control.Monad.State.Strict the strict version, that's much less intrusive.
Cheers, Simon
It is foreseeable that complicated Monads mighty have more intermediate levels of Strictness (in the tuple, in the return value, in part of the state ...). The module name space accommodates this better than counting primes on State''', and the "import qualified" syntax makes changing imports transparent to the rest of the file. -- Chris
On Wed, Jan 31, 2007 at 03:48:25PM +0000, Ian Lynagh wrote:
instance Monad (State s) where return a = State $ \s -> (a, s) m >>= k = State $ \s -> case runState m s of (a, s') -> runState (k a) $! s'
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
We agreed on IRC that the $!'s solve an orthogonal problem so the strict monads will just have: instance Monad (State s) where return a = State $ \s -> (a, s) m >>= k = State $ \s -> case runState m s of (a, s') -> runState (k a) s' 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 Thanks Ian
On Wed, Jan 31, 2007 at 03:48:25PM +0000, Ian Lynagh wrote:
Control.Monad.State.Class -- for the MonadState class Control.Monad.State.Lazy Control.Monad.State.Strict Control.Monad.State -- re-exports .Class and .Lazy
Now done. Here's the patch description:
[Rejig mtl; trac proposal #1127
Ian Lynagh
participants (5)
-
Chris Kuklewicz -
dons＠cse.unsw.edu.au -
Ian Lynagh -
Neil Mitchell -
Simon Marlow