s c h e m a t i c s : c o o k b o o k

This Web

Other Webs

Schematics

RSS

Scheme Links

Building a Circular List

Problem

Solution

> (define rb '(1 2 3 4))
> (set-cdr! (last-pair rb) rb)
> rb
#0=(1 2 3 4 . #0#)

Note the odd notation the #0= at the start and the . #0# on the tail is telling you the list is circular. Look at what the result of cdr is:

> (cdr rb)
#0=(2 3 4 1 . #0#)

Discussion

Circular lists do require care when you're working with list functions, many functions will not accept a circular list, or will not terminate when given one. The problem is in detecting the head of the list; if list elements aren't unique, you can't simply check if you've seen an element before. In the ring buffer case, you probably have a fixed size ring buffer, so it's easiest just to keep track of how many elements you've seen when traversing a list and comparing to the known length.

SRFI-1 also has functions circular-list for building circular lists and circular-list? for determining if a list is circular.

> (circular-list 1 2 3 4)
#0=(1 2 3 4 . #0#)

Comments about this recipe

Contributors

-- GordonWeakliem - 12 Aug 2004