What are circular lists good for (in Lisp or Scheme)?

Question

I note that Scheme and Lisp (I guess) support circular lists, and I have used circular lists in C/C++ to 'simplify' the insertion and deletion of elements, but what are they good for?

Scheme ensures that they can be built and processed, but for what?

Is there a 'killer' data structure that needs to be circular or tail-circular?

Answer 1

Saying it supports 'circular lists' is a bit much. You can build all kinds of circular data structures in Lisp. Like in many programming languages. There is not much special about Lisp in this respect. Take your typical 'Algorithms and Datastructure' book and implement any circular data structure: graphs, rings, ... What some Lisps offer is that one can print and read circular data structures. The support for this is because in typical Lisp programming domains circular data structures are common: parsers, relational expressions, networks of words, plans, ...

It is quite common that data structures contain cycles. Real 'circular lists' are not that often used. For example think of a task scheduler which runs a task and after some time switches to the next. The list of tasks can be circular so that after the 'last' task the scheduler takes the 'first' task. In fact there is no 'last' and 'first' - it is just a circular list of tasks and the scheduler runs them without end. You could also have a list of windows in a window system and with some key command you would switch to the next window. The list of windows could be circular.

Lists are useful when you need a cheap next operation and the size of the data structure is unknown in advance. You can always add another node to the list or remove a node from a list. Usual implementations of lists make getting the next node and adding/removing an item cheap. Getting the next element from an array is also relatively simple (increase the index, at the last index go to the first index), but adding/removing elements usually needs more expensive shift operations.

Also since it is easy to build circular data structures, one just might do it during interactive programming. If you then print a circular data structure with the built-in routines it would be a good idea if the printer can handle it, since otherwise it may print a circular list forever...

Answer 2

Have you ever played Monopoly?

Without playing games with counters and modulo and such, how would you represent the Monopoly board in a computer implementation of the game? A circular list is a natural.

Answer 3

For example a double linked list data structure is "circular" in the Scheme/LISP point of view, i.e. if you try to print the cons-structure out you get backreferences, i.e. "cycles". So it's not really about having data structures that look like "rings", any data structure where you have some kind of backpointers is "circular" from the Scheme/LISP perspective.

A "normal" LISP list is single linked, which means that a destructive mutation to remove an item from inside the list is an O(n) operation; for double linked lists it is O(1). That's the "killer feature" of double linked lists, which are "circular" in the Scheme/LISP context.

Answer 4

Adding and removing elements to the beginning of a list is cheap. To add or remove an element from the end of a list, you have to traverse the whole list.

With a circular list, you can have a sort of fixed-length queue.

Setup a circular list of length 5:

> (import (srfi :1 lists))
> (define q (circular-list 1 2 3 4 5))

Let's add a number to the list:

 > (set-car! q 6)

Now, let's make that the last element of the list:

 > (set! q (cdr q))

Display the list:

 > (take q 5)
 (2 3 4 5 6)

So you can view this as a queue where elements enter at the end of the list and are removed from the head.

Let's add 7 to the list:

> (set-car! q 7)
> (set!     q (cdr q))
> (take q 5)
(3 4 5 6 7)

Etc...

Anyways, this is one way that I've used circular-lists.

I use this technique in an OpenGL demo which I ported from an example in the Processing book.

Ed

Answer 5

One use of circular lists is to "repeat" values when using the srfi-1 version of map. For example, to add val to each element of lst, we could write:

(map + (circular-list val) lst)

For example:

(map + (circular-list 10) (list 0 1 2 3 4 5))

returns:

(10 11 12 13 14 15)

Of course, you could do this by replacing + with (lambda (x) (+ x val)), but sometimes the above idiom can be handier. Note that this only works with the srfi-1 version of map, which can accept lists of different sizes.