On Tue, May 26, 2009 at 5:03 PM, Daryoush Mehrtash
newtype Parser s a = P( [s] -> Maybe (a, [s])) (fixed typo)
instance MonadPlus Parser where P a mplus P b = P (\s -> case a s of Just (x, s') -> Just (x, s') Nothing -> b s)
a)what exactly gets saved on the heap between the mplus calls?
Two things: (1) Values in the input stream that "a" parses before failing. Beforehand, it might just be a thunk that generates the list lazily in some fashion. (2) The state of the closure "b"; if parser "a" fails, we need to be able to run "b"; that could use an arbitrary amount of space depending on what data it keeps alive.
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?
Nope, no IO involved; just look at the types: P :: ([s] -> Maybe (a,[s])) -> Parser s a (Parser s a) is just a function that takes a list of "s", and possibly returns a value of type "a" and another list [s] (of the remaining tokens, one hopes) It's up to the caller of the parsing function to provide the token stream [s] somehow.
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?
It just passes the same stream to both. No mutability means no danger :) -- ryan