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

[Daryoush Mehrtash]

In Section 2.5 of "Generalizing Monads to Arrows" paper
(link<http://www.cs.chalmers.se/%7Erjmh/Papers/arrows.ps>)
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
understand...

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
reused?
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?

Thanks,

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