<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD> <META content="text/html; charset=us-ascii" http-equiv=Content-Type> <META name=GENERATOR content="MSHTML 9.00.8112.16434"></HEAD> <BODY> <DIV dir=ltr align=left><SPAN class=945504210-30082011><FONT face=Arial><FONT color=#0000ff size=2>You are stating: hash with bounded memory</FONT></FONT></SPAN></DIV> <DIV dir=ltr align=left><SPAN class=945504210-30082011><FONT color=#0000ff size=2 face=Arial>Does that mean you will have a limit on the number of entries?</FONT></SPAN></DIV> <DIV dir=ltr align=left><SPAN class=945504210-30082011><FONT color=#0000ff size=2 face=Arial>In that case a vector plus a current index might do, I think.</FONT></SPAN></DIV> <DIV dir=ltr align=left><SPAN class=945504210-30082011><FONT color=#0000ff size=2 face=Arial>Gives you O(1) access to every element.</FONT></SPAN></DIV> <DIV dir=ltr align=left><SPAN class=945504210-30082011><FONT color=#0000ff size=2 face=Arial>If the required number of elements may vary very much, a vector probably is not a good idea, unless using resizable vectors, but that makes some operations O(n).</FONT></SPAN></DIV> <DIV dir=ltr align=left><SPAN class=945504210-30082011></SPAN> </DIV> <DIV dir=ltr align=left><SPAN class=945504210-30082011></SPAN><SPAN class=945504210-30082011><FONT color=#0000ff size=2 face=Arial>BTW, I like the two posts of  Neil Toronto and Danny Yoo.</FONT></SPAN></DIV> <DIV dir=ltr align=left><SPAN class=945504210-30082011><FONT color=#0000ff size=2 face=Arial></FONT></SPAN> </DIV> <DIV dir=ltr align=left><SPAN class=945504210-30082011><FONT color=#0000ff size=2 face=Arial>Jos</FONT></SPAN></DIV><BR> <DIV dir=ltr lang=en-us class=OutlookMessageHeader align=left> <HR tabIndex=-1> <FONT size=2 face=Tahoma><B>From:</B> users-bounces@racket-lang.org [mailto:users-bounces@racket-lang.org] <B>On Behalf Of </B>Laurent<BR><B>Sent:</B> martes, 30 de agosto de 2011 9:18<BR><B>To:</B> Danny Yoo<BR><B>Cc:</B> users@racket-lang.org<BR><B>Subject:</B> Re: [racket] doubly linked list lib<BR></FONT><BR></DIV> <DIV></DIV>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>I started my own lib, but if something already exists, I'm still interested.<BR><BR>The purpose is to make a hash with bounded memory, with replacement of oldest items, or barely used items, or some other replacement criterion.<BR><BR>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.<BR><BR>I'll keep the zipper in mind for other purposes though!<BR><BR>Laurent<BR><BR> <DIV class=gmail_quote>On Tue, Aug 30, 2011 at 08:35, Danny Yoo <SPAN dir=ltr><<A href="mailto:dyoo@cs.wpi.edu">dyoo@cs.wpi.edu</A>></SPAN> wrote:<BR> <BLOCKQUOTE style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class=gmail_quote> <DIV class=im>> Nothing obvious, no. But Racket is designed to encourage programming without<BR>> mutation, and doubly linked lists require mutation.<BR>><BR>> It's very likely a zipper will do what you want. A zipper is much easier to<BR>> implement than a doubly linked list, and has similar performance and uses.<BR><BR><BR></DIV>To supplement, here are very old notes I wrote to myself on the kind<BR>of list zipper that Neil is presenting:<BR><BR>   <A href="https://hkn.eecs.berkeley.edu/%7Edyoo/plt/zippers.txt" target=_blank>https://hkn.eecs.berkeley.edu/~dyoo/plt/zippers.txt</A><BR> <DIV> <DIV></DIV> <DIV class=h5>_________________________________________________<BR> For list-related administrative tasks:<BR> <A href="http://lists.racket-lang.org/listinfo/users" target=_blank>http://lists.racket-lang.org/listinfo/users</A><BR></DIV></DIV></BLOCKQUOTE></DIV><BR></BODY></HTML>