[Haskell-cafe] Space usage problems

[Ian Lynagh]

On Tue, Jan 10, 2006 at 05:28:03PM +0000, Chris Kuklewicz wrote:
> I'll make a guess...
> 
> Ian Lynagh wrote:
> > Hi all,
> > 
> > foo :: String -> (String, String)
> > foo = runState bar
> > 
> > bar :: SecondMonad String
> > bar = do inp <- get
> >          case inp of
> >              [] -> return []
> >              x:xs -> do put xs
> >                         liftM (x:) bar
> The liftM should be equivalent to
>                           temp <- bar
>                           return ( (x:) temp )
> 
> It looks like the first call to foo will have bar consuming the entire
> input string.

I'm not entirely sure what you mean here. The result will be the entire
input string, but State is a lazy monad, so it won't have to consume it
all before it starts returning it.

For example, if you replace the definition of foo with

    foo xs = (evalState bar xs, "")

then the program runs in constant space (but this isn't a solution to
the real problem, as bar will only consume a prefix of the string
there).


Thanks
Ian