[Haskell-cafe] Space usage problems

Chris Kuklewicz haskell at list.mightyreason.com
Tue Jan 10 12:55:38 EST 2006


I will continue to guess...

Ian Lynagh wrote:
> 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).
> 
Yes, exactly as I would have predicted.

Your "let (yx,zs) = foo xs
      put zs"
takes the second of the tuple retuned from "foo = runState bar" and
put's it.  Then in the recursive readChucks call, it does
      xs <- get
      if (null xs)

So it has to decide if xs (which is zs which is the snd value from foo
which is the state from runState bar which is "" or []) is null or not.

This forces it to get the head of the String state that bar returns, or
[] since there is no head.  But it does not know that it is [] until bar
is fully finished, which loads the whole file into memory.

When you put (evalState bar xs, "") then zs is [] and put [] leads to
get [] and null [] is true so it returns [] to the nested readChunks
call.  This does not force the file to be read.


More information about the Haskell-Cafe mailing list