Thank you very much, that looks good.<br><br>Laurent<br><br><div class="gmail_quote">On Tue, Aug 30, 2011 at 17:08, Sam Tobin-Hochstadt <span dir="ltr">&lt;<a href="mailto:samth@ccs.neu.edu">samth@ccs.neu.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;">I think there are some purely functional data structures that you can<br>
use here.  Two examples:<br>
<br>
 - Random Access Lists implemented in Hari Prashanth&#39;s Typed Purely<br>
Functional Data Structures [1]<br>
   Some of the other data structures here, such as VLists, may also be helpful.<br>
<br>
 - David Van Horn&#39;s RAList package [2]<br>
<br>
[1] <a href="http://planet.plt-scheme.org/package-source/krhari/pfds.plt/1/5/planet-docs/functional-data-structures/Random_Access_Lists.html" target="_blank">http://planet.plt-scheme.org/package-source/krhari/pfds.plt/1/5/planet-docs/functional-data-structures/Random_Access_Lists.html</a><br>


[2] <a href="http://planet.racket-lang.org/display.ss?package=ralist.plt&amp;owner=dvanhorn" target="_blank">http://planet.racket-lang.org/display.ss?package=ralist.plt&amp;owner=dvanhorn</a><br>
<div><div></div><div class="h5"><br>
On Tue, Aug 30, 2011 at 3:18 AM, Laurent &lt;<a href="mailto:laurent.orseau@gmail.com">laurent.orseau@gmail.com</a>&gt; wrote:<br>
&gt; Thank you very much for this nice intermediate solution, though I need<br>
&gt; constant-time append, split, insert, remove, + pointers to items, etc.<br>
&gt; Mutation does seem unavoidable, right.<br>
&gt; I started my own lib, but if something already exists, I&#39;m still interested.<br>
&gt;<br>
&gt; The purpose is to make a hash with bounded memory, with replacement of<br>
&gt; oldest items, or barely used items, or some other replacement criterion.<br>
&gt;<br>
&gt; The final purpose is to make a memoization form with bounded memory, or<br>
&gt; growing memory but with frequent removal of selected items. If I have time<br>
&gt; to get there.<br>
&gt;<br>
&gt; I&#39;ll keep the zipper in mind for other purposes though!<br>
&gt;<br>
&gt; Laurent<br>
&gt;<br>
&gt; On Tue, Aug 30, 2011 at 08:35, Danny Yoo &lt;<a href="mailto:dyoo@cs.wpi.edu">dyoo@cs.wpi.edu</a>&gt; wrote:<br>
&gt;&gt;<br>
&gt;&gt; &gt; Nothing obvious, no. But Racket is designed to encourage programming<br>
&gt;&gt; &gt; without<br>
&gt;&gt; &gt; mutation, and doubly linked lists require mutation.<br>
&gt;&gt; &gt;<br>
&gt;&gt; &gt; It&#39;s very likely a zipper will do what you want. A zipper is much easier<br>
&gt;&gt; &gt; to<br>
&gt;&gt; &gt; implement than a doubly linked list, and has similar performance and<br>
&gt;&gt; &gt; uses.<br>
&gt;&gt;<br>
&gt;&gt;<br>
&gt;&gt; To supplement, here are very old notes I wrote to myself on the kind<br>
&gt;&gt; of list zipper that Neil is presenting:<br>
&gt;&gt;<br>
&gt;&gt;    <a href="https://hkn.eecs.berkeley.edu/%7Edyoo/plt/zippers.txt" target="_blank">https://hkn.eecs.berkeley.edu/~dyoo/plt/zippers.txt</a><br>
&gt;&gt; _________________________________________________<br>
&gt;&gt;  For list-related administrative tasks:<br>
&gt;&gt;  <a href="http://lists.racket-lang.org/listinfo/users" target="_blank">http://lists.racket-lang.org/listinfo/users</a><br>
&gt;<br>
&gt;<br>
&gt; _________________________________________________<br>
&gt;  For list-related administrative tasks:<br>
&gt;  <a href="http://lists.racket-lang.org/listinfo/users" target="_blank">http://lists.racket-lang.org/listinfo/users</a><br>
&gt;<br>
<br>
<br>
<br>
</div></div><font color="#888888">--<br>
sam th<br>
<a href="mailto:samth@ccs.neu.edu">samth@ccs.neu.edu</a><br>
</font></blockquote></div><br>