[racket] doubly linked list lib

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-bounces at racket-lang.org [mailto:users-bounces at racket-lang.org]
On Behalf Of Laurent
Sent: martes, 30 de agosto de 2011 9:18
To: Danny Yoo
Cc: users at 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 <dyoo at 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



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20110830/39af3e8c/attachment.html>