On Tue, May 26, 2009 at 6:11 PM, Ryan Ingram <ryani.spam@gmail.com> wrote:

On Tue, May 26, 2009 at 5:03 PM, Daryoush Mehrtash <dmehrtash@gmail.com> wrote:
> 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