<br><br><div class="gmail_quote">On Tue, Aug 30, 2011 at 12:23, Stephen Bloch <span dir="ltr">&lt;<a href="mailto:sbloch@adelphi.edu">sbloch@adelphi.edu</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">

<div style="word-wrap: break-word;">
<br><div><div class="im"><div>On Aug 30, 2011, at 3:18 AM, Laurent wrote:</div><br><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></div>The &quot;zipper&quot; structure Neil posted has constant-time append if you&#39;re already at the head of one zipper and the tail of the other, but in general it&#39;ll be linear time.  It has constant-time split, insert, and remove.</div>

</div></blockquote><div><br>Not if you are not already at the right place in the lists.<br>Finding the place of the element in the list would take linear time.<br> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">

<div style="word-wrap: break-word;"><div>  What do you mean by &quot;pointers to items&quot; -- that is, what do you need to DO with pointers to items?</div></div></blockquote><div><br>Items are struct instances. By pointers I meant references, as they are handled automatically in Racket.<br>

The list of items gives me a modifiable preference order on the items (the preference criterion may vary).<br>
Each hash entry holds a &quot;reference&quot; to an item, and an item holds a reference to the previous and next elements in the list.<br>For example, given a key in the hash I get the reference to the item, and I can then put that element at the end of the list, or exchange it with the next element, or remove it, etc.<br>

This does not seem possible with the same time complexity with zippers.<br><br>Laurent<br><br></div></div>