[Haskell-cafe] trying to understand space leaks....

Daryoush Mehrtash dmehrtash at gmail.com
Tue May 26 20:03:05 EDT 2009

In Section 2.5 of "Generalizing Monads to Arrows" paper
John Huges talks about the space leak inherit in monadic implementation of
backtracking parsers.

newtype Parser s a = P( [s] => Maybe (a, [s]))

instance MonadPlus  Parser where
      P a mplus P b = P (\s -> case a s of
                            Just (x, s') -> Just (x, s')
                            Nothing -> b s)

The problem (as I understand it) is that to implement the backtracking, the
monad plus implementation needs to keep the state (the computation that
returns the next token) around in case the parser fails (so that it can be
passed to the other side of mplus).    I am having hard time to

a)what exactly gets saved on the heap between the mplus calls?
b)I am assuming the computation to get the next character for parsing to be
an "IO Char" type computation,  in that case, what would be the size of the
heap buffer that is kept around in case the computation result needs to be
c) Assuming Pa in the above code reads n tokens from the input stream then
fails, how does the run time returns the same token to the P b?


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090526/3329917f/attachment.html

More information about the Haskell-Cafe mailing list