[racket] doubly linked list lib

From: Sam Tobin-Hochstadt (samth at ccs.neu.edu)
Date: Tue Aug 30 11:08:37 EDT 2011

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] http://planet.plt-scheme.org/package-source/krhari/pfds.plt/1/5/planet-docs/functional-data-structures/Random_Access_Lists.html
[2] http://planet.racket-lang.org/display.ss?package=ralist.plt&owner=dvanhorn

On Tue, Aug 30, 2011 at 3:18 AM, Laurent <laurent.orseau at gmail.com> 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 <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
>> _________________________________________________
>>  For list-related administrative tasks:
>>  http://lists.racket-lang.org/listinfo/users
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/users

sam th
samth at ccs.neu.edu

Posted on the users mailing list.