[plt-scheme] self-referential data structures

2009/3/5 Stephen Bloch <sbloch at adelphi.edu>:
> However, there are more complicated self-referential data types that are
> difficult to do without mutation.  For example, consider
> (define biglist (list 10 9 8 7 6 5 4 3 2 1 0))
> (define partlist (rest (rest (rest (rest biglist)))))
> From "partlist", you can easily get the 5th element of the original list, or
> move forward to the the 6th element and so on... but there's no way to "move
> backward" through the original list to see the 3rd element of the original
> list, because "partlist" doesn't contain that information.  For some
> applications it's very useful to be able to move both backward and forward
> through a large list, and the usual data structure to do that is called a
> "doubly linked list".  Since the 5th element of a list has to "know" about
> both the 4th and 6th elements, both of which have to "know" about the 5th,
> the usual way to build a doubly linked list is to create the 6th element,
> then create the 5th element referring to it, then MUTATE the 6th element so
> that it knows about the 5th element in turn, then create the 4th element
> referring to the 5th element, then MUTATE the 5th element so  it knows about
> the 4th element, and so  on.  This is difficult to do without mutation.

You could also do something like this:

; file dlist.ss
#lang scheme/base

(provide dlist previous next current)

(define-struct triplet (previous current next))

(define (dlist x . xs)
  (make-triplet '() x xs))

(define (previous dlist)
  (make-triplet (cdr (triplet-previous dlist))
                (car (triplet-previous dlist))
                (cons (triplet-current dlist)
                      (triplet-next dlist))))

(define (next dlist)
  (make-triplet (cons (triplet-current dlist)
                      (triplet-previous dlist))
                (car (triplet-next dlist))
                (cdr (triplet-next dlist))))

(define current triplet-current)

; repl
> (define biglist (dlist 10 9 8 7 6 5 4 3 2 1 0))
> (define partlist (next (next (next (next biglist)))))
> (current partlist)
6
> (define going-back (previous (previous partlist)))
> (current going-back)
8

I used a data structure like this for a Turing Machine simulator I
wrote a few years ago, it implements a tape as two stacks, and can be
simply extended to support cheap functional update. In my use of it,
though, the tape was boundless, so I was using bottomless stacks.

    Henk