You are stating: hash with bounded memory Does that mean you will have a limit on the number of entries? In that case a vector plus a current index might do, I think. Gives you O(1) access to every element. 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). BTW, I like the two posts of Neil Toronto and Danny Yoo. Jos
_____ From: users-boun...@racket-lang.org [mailto:users-boun...@racket-lang.org] On Behalf Of Laurent Sent: martes, 30 de agosto de 2011 9:18 To: Danny Yoo Cc: users@racket-lang.org Subject: Re: [racket] doubly linked list lib 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 <d...@cs.wpi.edu> 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: https://hkn.eecs.berkeley.edu/~dyoo/plt/zippers.txt <https://hkn.eecs.berkeley.edu/%7Edyoo/plt/zippers.txt> _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
_________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
