Circular list in Common Lisp

Question

I am working using a visual programming environment for musical composition based on CL . I am trying to create a function that when given say 3 elements (1 2 3) will return 1, 2, 3, 1, 2, 3 etc., one number at the time each time it is evaluated. The book Common Lisp a Gentle Introduction, mentions briefly that it's possible to create circular lists using sharp-equal notation but does not get into details on how to use them. Keep in mind that I can insert actual Lisp code in the program using a object specifically designed for that.

Bouchard

Also see Lisp cyclic lists and Example of Sharpsign Equal-Sign reader macro. – Prehension

Answer 1

CL-USER 3 > (defun circular (items)
              (setf (cdr (last items)) items)
              items)
CIRCULAR

CL-USER 4 > (setf *print-circle* t)
T

CL-USER 5 > (circular (list 1 2 3))
#1=(1 2 3 . #1#)

Example:

CL-USER 16 > (setf c1 (circular (list 1 2 3)))
#1=(1 2 3 . #1#)

CL-USER 17 > (pop c1)
1

CL-USER 18 > (pop c1)
2

CL-USER 19 > (pop c1)
3

CL-USER 20 > (pop c1)
1

also:

CL-USER 6 > '#1=(1 2 3 . #1#)
#1=(1 2 3 . #1#)

With a bit of CLOS added:

(defclass circular ()
  ((items :initarg :items)))

(defmethod initialize-instance :after ((c circular) &rest initargs)
  (setf (slot-value c 'items) (circular (slot-value c 'items))))

(defmethod next-item ((c circular))
  (prog1 (first (slot-value c 'items))
    (setf (slot-value c 'items)
          (rest (slot-value c 'items)))))

CL-USER 7 > (setf circ1 (make-instance 'circular :items (list 1 2 3)))
#<CIRCULAR 40200017CB>

CL-USER 8 > (next-item circ1)
1

CL-USER 9 > (next-item circ1)
2

CL-USER 10 > (next-item circ1)
3

CL-USER 11 > (next-item circ1)
1

CL-USER 12 > (next-item circ1)
2

Christi

Are there any books or sites you suggest that would help me learn more about this type of thing? – Bouchard

There's a section in Let Over Lambda on cyclic expressions: letoverlambda.com/index.cl/guest/chap4.html#sec_5 – Rainmaker

There is no need to return items in the definition of circular as setf will return it anyway. – Arabian

@tsikov: yes, but I wanted it to be clearer in the source and not to depend on the knowledge of the reader. – Christi

Answer 2

In Sharpsign Equal-Sign notation, it's written as #0=(1 2 3 . #0#).

Here's a function which creates such a list from the given arguments:

(defun circular (first &rest rest)
  (let ((items (cons first rest)))
    (setf (cdr (last items)) items)))

Then, calling (circular 1 2 3) will return the circular list you wanted. Just use car and cdr to iterate through the elements ad infinitum.

And if you really want an iterator function that takes no arguments and returns the next item for each call, here's how you might do it:

(defun make-iter (list)
  (lambda ()
    (pop list)))

Sprage

You could use PROG1 instead of LET. – Villalobos

@ThomasBartscher Thanks! It's now implemented. (Actually I looked at Rainer's answer and it seems pop does the same thing as what I'm after. That's what happens when a Schemer tries to write CL. ;-)) – Sprage

Huh, I didn't think of that. Nice! – Villalobos

Answer 3

First, you want to let the printer know to recognize circular lists instead of trying to print the whole list:

(setf *print-circle* t)

Next, you can create a circular list using the Sharpsign Equal-Sign notation:

(setq x '#1=(1 2 3 . #1#))

Swashbuckler

Answer 4

Here is an idea worked out for a circular list in Lisp.

;;; Showing structure of the list
;;; (next prev is-end val)

; create items
setf L-0 (L-1 L-3 t "L-0 sentry")  ; this will be the sentry item so know where to stop
setf L-1 (L-2 L-0 nil "L-1")
setf L-2 (L-3 L-1 nil "L-2")
setf L-3 (L-0 L-2 nil "L-3")

; how to access L-2 from L-0
eval (first (eval (first L-0)))

; result: (L-3 L-1 NIL "L-2")

I'm not giving defun functions to make adding, removing, and accessing the items. I'm thinking that what I gave is enough to show what you need to do in any functions you define for this kind of circular list. This appeared to me to work in the Listener.

Rosabella