On 08/29/2011 06:13 AM, Laurent wrote:
Hi,
It seems highly probable that there exists a doubly linked list library
somewhere, but I couldn't find any.
Does anyone know about something like that or should I make my own? (or
is there something obvious that I completely miss?)
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.
Here's a quick implementation:
#lang racket
(struct zipper (head current tail) #:transparent)
(define (zipper-next z)
(match-define (zipper h c t) z)
(zipper (cons c h) (first t) (rest t)))
(define (zipper-prev z)
(match-define (zipper h c t) z)
(zipper (rest h) (first h) (cons c t)))
(define (zipper-set z new-current)
(match-define (zipper h _ t) z)
(zipper h new-current t))
(define (list->zipper lst)
(zipper empty (first lst) (rest lst)))
(define (zipper->list z)
(match-define (zipper h c t) z)
(append (reverse h) (list c) t))
; tests: replace 2 and 3 with 20 and 30
(define z1 (list->zipper '(1 2 3 4)))
(define z2 (zipper-next z1))
(define z3 (zipper-set z2 20))
(define z4 (zipper-next z3))
(define z5 (zipper-next z4))
(define z6 (zipper-prev z5))
(define z7 (zipper-set z6 30))
(zipper->list z7)
(zipper->list z3) ; just the 2 is different
A zipper is like a cursor. It has a current element, the stuff before
the current element (head), and the stuff after (tail). There are
functions to move forward (zipper-next) and back (zipper-prev). Both
return a new zipper, with a different current element.
The only tricky part is that the head is stored in reverse order to make
it easier to grab the "last" element in the head in zipper-prev. In
reverse order, the "last" element is the first.
Neil T
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users
