[Haskell-cafe] trying to understand space leaks....
ryani.spam at gmail.com
Tue May 26 21:11:56 EDT 2009
On Tue, May 26, 2009 at 5:03 PM, Daryoush Mehrtash <dmehrtash at gmail.com> wrote:
> 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)
> a)what exactly gets saved on the heap between the mplus calls?
(1) Values in the input stream that "a" parses before failing.
Beforehand, it might just be a thunk that generates the list lazily in
(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
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 :)
More information about the Haskell-Cafe