[plt-scheme] self-referential data structures

On Mar 5, 2009, at 11:15 PM, Henk Boom wrote:

> 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)

I have to confess, I hadn't thought of that, and now I feel stupid  
for not having thought of it.  Especially since I've done the  
standard simulation of a Turing machine by a two-stack PDA.

When I first looked at it, I thought "Yes, but won't that be terribly  
inefficient?"  And then I thought "Even worse, (next (previous my- 
list)) isn't equal? to my-list."  On a second look, I realized I was  
incorrect about the second objection (it isn't eqv?, but it is  
equal?), and any extra triplets you create in the course of moving  
back and forth along a list can be garbage-collected, so the  
efficiency difference comes down to a (small) constant factor of both  
time and memory.  And, of course, efficiency is seldom a serious  
concern in a first course; you optimize after you've got things  
working correctly.

I wouldn't want to do the above in a non-garbage-collected language,  
but then again I'd rather not do much of ANYTHING in a non-garbage- 
collected language :-)

Thanks, Henk and Marco: I learned something today.



Stephen Bloch
sbloch at adelphi.edu