[Haskell-cafe] trying to understand space leaks....
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
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...
More information about the Haskell-Cafe