So long as the [s] is a fixed list (say [1,2,3,4]) there is no space leak. My understanding was that the space leak only happens if there is computation involved in building the list of s. Am I correct?<br><br>If so, I still don't have any feeling for what needs to be saved on the heap to be able to back track on computation that needs and IO computation data. What would be approximate space that an IO (Char) computation take on the heap, is it few bytes, 100, 1k, ....?<br>
<br>Daryoush<br><br><br><div class="gmail_quote">On Tue, May 26, 2009 at 6:11 PM, Ryan Ingram <span dir="ltr"><<a href="mailto:ryani.spam@gmail.com">ryani.spam@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="im">On Tue, May 26, 2009 at 5:03 PM, Daryoush Mehrtash <<a href="mailto:dmehrtash@gmail.com">dmehrtash@gmail.com</a>> wrote:<br>
> newtype Parser s a = P( [s] -> Maybe (a, [s]))<br>
</div>(fixed typo)<br>
<div class="im"><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>
</div><div class="im">> a)what exactly gets saved on the heap between the mplus calls?<br>
<br>
</div>Two things:<br>
<br>
(1) Values in the input stream that "a" parses before failing.<br>
Beforehand, it might just be a thunk that generates the list lazily in<br>
some fashion.<br>
<br>
(2) The state of the closure "b"; if parser "a" fails, we need to be<br>
able to run "b"; that could use an arbitrary amount of space depending<br>
on what data it keeps alive.<br>
<div class="im"><br>
> b)I am assuming the computation to get the next character for parsing to be<br>
> an "IO Char" type computation, in that case, what would be the size of the<br>
> heap buffer that is kept around in case the computation result needs to be<br>
> reused?<br>
<br>
</div>Nope, no IO involved; just look at the types:<br>
<br>
P :: ([s] -> Maybe (a,[s])) -> Parser s a<br>
<br>
(Parser s a) is just a function that takes a list of "s", and possibly<br>
returns a value of type "a" and another list [s] (of the remaining<br>
tokens, one hopes)<br>
<br>
It's up to the caller of the parsing function to provide the token<br>
stream [s] somehow.<br>
<div class="im"><br>
> c) Assuming Pa in the above code reads n tokens from the input stream then<br>
> fails, how does the run time returns the same token to the P b?<br>
<br>
</div>It just passes the same stream to both. No mutability means no danger :)<br>
<font color="#888888"><br>
-- ryan<br>
</font></blockquote></div><br><br>