<br><br><div class="gmail_quote">On Tue, Aug 30, 2011 at 12:23, Stephen Bloch <span dir="ltr"><<a href="mailto:sbloch@adelphi.edu">sbloch@adelphi.edu</a>></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 "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.</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 "pointers to items" -- 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 "reference" 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>