Thank you very much, that looks good. Laurent <div class="gmail_quote">On Tue, Aug 30, 2011 at 17:08, Sam Tobin-Hochstadt <<a href="mailto:samth@ccs.neu.edu">samth@ccs.neu.edu</a>> wrote: <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 use here. Two examples: - Random Access Lists implemented in Hari Prashanth's Typed Purely Functional Data Structures [1] Some of the other data structures here, such as VLists, may also be helpful. - David Van Horn's RAList package [2] [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> [2] <a href="http://planet.racket-lang.org/display.ss?package=ralist.plt&owner=dvanhorn" target="_blank">http://planet.racket-lang.org/display.ss?package=ralist.plt&owner=dvanhorn</a> <div><div></div><div class="h5"> On Tue, Aug 30, 2011 at 3:18 AM, Laurent <<a href="mailto:laurent.orseau@gmail.com">laurent.orseau@gmail.com</a>> wrote: > 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. > I started my own lib, but if something already exists, I'm still interested. > > The purpose is to make a hash with bounded memory, with replacement of > oldest items, or barely used items, or some other replacement criterion. > > The final purpose is to make a memoization form with bounded memory, or > growing memory but with frequent removal of selected items. If I have time > to get there. > > I'll keep the zipper in mind for other purposes though! > > Laurent > > On Tue, Aug 30, 2011 at 08:35, Danny Yoo <<a href="mailto:dyoo@cs.wpi.edu">dyoo@cs.wpi.edu</a>> wrote: >> >> > Nothing obvious, no. But Racket is designed to encourage programming >> > without >> > mutation, and doubly linked lists require mutation. >> > >> > It's very likely a zipper will do what you want. A zipper is much easier >> > to >> > implement than a doubly linked list, and has similar performance and >> > uses. >> >> >> To supplement, here are very old notes I wrote to myself on the kind >> of list zipper that Neil is presenting: >> >> <a href="https://hkn.eecs.berkeley.edu/%7Edyoo/plt/zippers.txt" target="_blank">https://hkn.eecs.berkeley.edu/~dyoo/plt/zippers.txt</a> >> _________________________________________________ >> For list-related administrative tasks: >> <a href="http://lists.racket-lang.org/listinfo/users" target="_blank">http://lists.racket-lang.org/listinfo/users</a> > > > _________________________________________________ > For list-related administrative tasks: > <a href="http://lists.racket-lang.org/listinfo/users" target="_blank">http://lists.racket-lang.org/listinfo/users</a> > </div></div>-- sam th <a href="mailto:samth@ccs.neu.edu">samth@ccs.neu.edu</a> </blockquote></div>