[racket] doubly linked list lib

From: Jos Koot (jos.koot at telefonica.net)
Date: Tue Aug 30 06:52:19 EDT 2011

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.


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!


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
> mutation, and doubly linked lists require mutation.
> It's very likely a zipper will do what you want. A zipper is much easier
> 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:


 For list-related administrative tasks:

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

Posted on the users mailing list.