[racket] doubly linked list lib

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