In Section 2.5 of "Generalizing Monads to Arrows" paper (<a href="http://www.cs.chalmers.se/%7Erjmh/Papers/arrows.ps">link</a>) John Huges talks about the space leak inherit in monadic implementation of backtracking parsers. <br>
<br><br>newtype Parser s a = P( [s] => Maybe (a, [s]))<br><br><br>instance MonadPlus Parser where<br> P a mplus P b = P (\s -> case a s of <br> Just (x, s') -> Just (x, s')<br>
Nothing -> b s)<br><br><br>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...<br>
<br>a)what exactly gets saved on the heap between the mplus calls? <br>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?<br>
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?<br><br>Thanks,<br><br>Daryoush<br> <br><br><br>