<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>Matthew Brecknell wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div>Matthew Eastman said:<br><blockquote type="cite">i.e. popping Blue in [Red, Red, Blue, Red, Blue] would give [Red, Red, &nbsp;<br></blockquote><blockquote type="cite">Blue]<br></blockquote><br>Hmm, did you mean [Red,Blue] or [Red,Red,Red,Blue]? Judging by your<br>implementation of remUseless, I'm guessing the latter.</div></blockquote></div><br><div>Yes, I meant the latter. Popping Blue in [Red, Red, Blue, Red, Blue] should give [Red, Red, Red, Blue]. Sorry for the confusion, I shouldn't be writing emails at midnight I guess!</div><div><br></div><div><br></div><div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div><div>apfelmus wrote:</div><div><br></div><blockquote type="cite">...</blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"></blockquote><blockquote type="cite"><div><span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">Our lists&nbsp;</span>won't store any elements at all!<br><br>newtype List a = Length Int &nbsp;&nbsp;deriving (Eq,Show,Num)<br><br>Instead, we're only storing the length of the list, so that<br><br>&nbsp;empty list &nbsp;&nbsp;corresponds to &nbsp;&nbsp;0<br>&nbsp;tail &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;corresponds to &nbsp;&nbsp;n-1<br>&nbsp;++ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;corresponds to &nbsp;&nbsp;+<br><br></div></blockquote><blockquote type="cite">...</blockquote><blockquote type="cite"><div><br>Regards,<br>apfelmus<br></div></blockquote></div><br><div>Wow! That's a really clever way to think about a list. The way that you push blue elements is pretty interesting too, switching the positions of the lists and doing a regular push. Very insightful posts.</div><div><br></div><div>I'm slowly reading through Okasaki's thesis now, I'm not sure how much of it I'm understanding but it seems pretty interesting. I had no idea that functional (I suppose "persistent" is the correct word) data structures were so different from ephemeral ones.</div><div><br></div><div><br></div><div>Thomas Davie wrote:</div><div><br></div><div><blockquote type="cite">In this interprettation, here's what I think is an O(1) implementation:</blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">...</blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">rbPop :: Colour -> RBStack a -> RBStack a<br>rbPop c Empty = error "Empty Stack, can't pop"<br>rbPop c (More c' v asCs nextNonC)<br>&nbsp;| c == c' &nbsp;&nbsp;= asCs<br>&nbsp;| otherwise = rbPop c nextNonC</blockquote><blockquote type="cite">...</blockquote><div><font class="Apple-style-span" color="#144FAE"><span class="Apple-style-span" style="color: rgb(0, 0, 0); "><blockquote type="cite"><br></blockquote><br></span></font></div><div>Your pop doesn't seem to be in O(1) since you have to walk through the nextNonC stack if the colours don't match.</div><div><br></div><div>Thanks for the help everyone,</div><div>Matt</div></div></div></div></body></html>