[Haskell-cafe] Re: Space usage problems

[Bulat Ziganshin]

Hello Ian,

Monday, January 16, 2006, 12:52:42 AM, you wrote:

IL> OK, I have one library which provides

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

you can use strict state monad for this task. "strictness" here
designate that it evaluates higher level of state, but it don't fully
evaluates the state (which itslef is impossible without using DeepSeq
class technique). so, for example, when you perform something like
"state = tail state" the lazy state monad may store call to tail
function in the state field and not evaluate it before needed, while
strict state monad will evaluate this higher-level expression and
store exactly the lazy expression that represents remainder of list

it's interesting that your work has a lot of common with my
Binary/Streams library. i'm used the same monadic types to define char
enocding/decoding routines (see DataCharEncoding.hs), i've defined
universal "mutable references" interface to transparently work with
variables in IO/ST monads, i've extended John's
StringReader/StringBuffer types to work in any monad. hust now i'm
working on extending my "ByteStream->BitStream" transformer to also
support any monads

although i'm not sure that Haskell implementation of inflate/deflate
algorithms will be a useful (just because it will be 100-1000 times
slower than existing C routines), nevertheless i glad to offer my
help, especially in optimizing code and making it monad-neutral

in particular, looking at your code in MissingH 0.13, i recommend you
try to use DiffUArray instead of Array

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

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

btw, "reading headers" is an perfect task for my Binary library. the
ony difference is what in your library "getBits" is an built-in
operation of special InfM monad, while in my library "getBits"
operation is applied to the Stream objects, but nevertheless work in
any monad (to be exact, it works in the monad, to which this Stream
obect belongs):

getBits :: (Monad m, Stream m h) => Int -> h -> m Int

"getBits bits h" returns 'bits' bits read from stream 'h'

most of types supporting Stream interface, works only in IO monad
(including Handle and MemoryBuffer), but at least StringReader &
StringBuffer types can be specialized to IO and ST monads and, in
general, to any monad, which is able to support readRef/writeRef
operations

if you want, you can try to implement the whole inflate process on top
of my Binary/Streams library, using these `getBits` operations.
something like these:

-- 's' is String containing your input data
runST (do h <- openBitAlignedLE =<< newStringReader s
          ... -- here you can use `getBits bits h` to read `s` as bits sequence
          return ...)

ps: http://freearc.narod.ru/Binary.tar.gz

-- 
Best regards,
 Bulat                            mailto:bulatz at HotPOP.com