[Haskell-cafe] Re: Space usage problems

[Ian Lynagh]

On Wed, Jan 11, 2006 at 03:00:45PM +0000, Simon Marlow wrote:
> Ian Lynagh wrote:
> >On Wed, Jan 11, 2006 at 10:36:47AM +0000, Simon Marlow wrote:
> >
> >>My suggestion: don't use the lazy state monad if you can help it.
> >
> >But a strict state monad would force everything to be loaded into memory
> >at once, right?
> >
> >What would you suggest I use instead?
> 
> I'm not sure - can you describe exactly what you want to do from a 
> higher level?  It might help to re-think the problem from the top down.

OK, I have one library which provides

    inflate :: [Word8]   -- The input
            -> ([Word8], -- A prefix of the input inflated (uncompressed)
                [Word8]) -- The remainder of the input

I can't tell how much of the input I'll be inflating in advance, I only
know when I reach the end of the compressed part.

Inflating has an array and a few other bits of state while it
uncompresses the input.

(I'm assuming the inflation won't fail for now; later I might want
something like
    inflate :: [Word8]   -- The input
            -> ([Word8], -- A prefix of the input, inflated (uncompressed)
                [Word8], -- The remainder of the input
                Bool)    -- Inflation failed
where you would need to write the inflated data to a file, say, before
checking the Bool to see if there was an error (if you want to work in
constant space)).

I'm happy to have a different type for inflate if necessary (e.g.
    inflate :: m [Word8] -> ([Word8] -> m ()) -> m [Word8]
where inflate uses the Monad of the caller to read and write the
remaining input; this leads to something using a monad transformer
for inflates other state, along the lines of Test2 in my original
message, which lead to a stack overflow) but it shouldn't be wedded to
the following library:


I then have another library with a function that does:

while (some input left)
    read header
    call inflate
    read footer
return (concat all the inflate results)

Reading headers is a fiddly enough task that passing the input around by
hand is undesirable.


Thanks
Ian