Proposal: Make StateT in mtl lazy

[Ian Lynagh]

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

-------------- next part --------------

import Control.Monad.Identity
import Control.Monad.State
import System.Environment

type M = StateT Char Identity

main = do [x] <- getArgs
          print $ head $ runIdentity $ evalStateT (f $ read x) 'a'

f :: Int -> M [Char]
f 0 = return []
f (n+1) = do st <- get
             rest <- f n
             return (st:rest)