<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "> <br><div><div>On Aug 30, 2011, at 3:18 AM, Laurent wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">Thank you very much for this nice intermediate solution, though I need constant-time append, split, insert, remove, + pointers to items, etc. Mutation does seem unavoidable, right.<br></blockquote><div><br></div>The "zipper" structure Neil posted has constant-time append if you're already at the head of one zipper and the tail of the other, but in general it'll be linear time.  It has constant-time split, insert, and remove.  What do you mean by "pointers to items" -- that is, what do you need to DO with pointers to items?</div><div><br></div><br><div> <span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div>Stephen Bloch</div><div><a href="mailto:sbloch@adelphi.edu">sbloch@adelphi.edu</a></div><div><br class="webkit-block-placeholder"></div></span><br class="Apple-interchange-newline"> </div><br></body></html>