Checking circularity in lisp - same variable through recursive function

Question

I'm trying to create a function that would test whether the given list is circular with a re-starting point being the beginning of the list.

Expected results:

(setq liste '(a b c))
(rplacd (cddr liste) liste)

(circular liste) => t
(circular '(a b c a b c)) => nil  

As I simply want to test if any subsequent item is 'eq' to the first one, I don't want to build the whole tortoise and hare algorithm.

Here is my code :

(defun circular (liste)
    (let (beginningliste (car liste)))
    (labels ( (circ2 (liste)
      (cond
        ((atom liste) nil)
        ((eq (car liste) beginningliste) t)
        (t (circ2 (cdr liste)))
        ) ) ) ) )

1. It doesn't give the expected result but I don't understand where my error is
2. I'm not sure I'm using 'labels' correctly
3. Is there a way to do that without using 'labels'?

---

Edit. I guess I have answered my third question as I think I have found a simpler way. Would this work?

(defun circular (liste)
   (cond
      ((atom liste) nil)
      ((eq (car liste) (cadr liste)) t)
      (t  (circular (rplacd liste  (cddr liste))))
      )
   )

Answer 1

First, the behavior is undefined when you mutate constant data: when you quote something (here the list), the Lisp environment has the right to treat it as a constant. See also this question for why defparameter or defvar is preferred over setq. And so...

(setq list '(a b c))
(rplacd (cddr list) list)

... would be better written as:

(defparameter *list* (copy-list '(a b c)))
(setf (cdr (last *list*)) *list*)

Second, your code is badly formatted and has bad naming conventions (please use dashes to separate words); here it is with a conventional layout, with the help of emacs:

(defun circularp (list)
  (let (first (car list)))
  (labels ((circ2 (list)
             (cond
               ((atom list) nil)
               ((eq (car list) first) t)
               (t (circ2 (cdr list))))))))

With that formatting, two things should be apparent:

• The let contains no body forms: you define local variables and never use them; you could as well delete the let line.

• Furthermore, the let is missing one pair of parenthesis: what you wrote defines a variable name first and another one named car, bound to list. I presume you want to define first as (car list).

• You define a local circ2 function but never use it. I would expect the circularp function (the -p is for "predicate", like numberp, stringp) to call (circ2 (cdr list)). I prefer renaming circ2 as visit (or recurse), because it means something.

With the above corrections, that would be:

(defun circularp (list)
  (let ((first (car list)))
    (labels ((visit (list)
               (cond
                 ((atom list) nil)
                 ((eq (car list) first) t)
                 (t (visit (cdr list))))))
      (visit (cdr list)))))

However, if your list is not circular but contains the same element multiple times (like '(a a b)), you will report it as circular, because you inspect the data it holds instead of the structure only. Don't look into the CAR here:

(defun circularp (list)
  (let ((first list))
    (labels ((visit (list)
               (cond
                 ((atom list) nil)
                 ((eq list first) t)
                 (t (visit (cdr list))))))
      (visit (cdr list)))))

Also, the inner function is tail recursive but there is no guarantee that a Common Lisp implementation automatically eliminates tail calls (you should check with your implementation; most can do it on request). That means you risk allocating as many call stack frames as you have elements in the list, which is bad. Better use a loop directly:

(defun circularp (list)
  (loop 
    for cursor on (cdr list)
    while (consp cursor)
    thereis (eq cursor list)))

Last, but not least: your approach is a very common one but fails when the list is not one big circular chain of cells, but merely contains a loop somewhere. Consider for example:

CL-USER> *list*
#1=(A B C . #1#)
CL-USER> (push 10 *list*)
(10 . #1=(A B C . #1#))
CL-USER> (push 20 *list*)
(20 10 . #1=(A B C . #1#))

(see that answer where I explain what #1= and #1# mean)

The lists with numbers in front exhibit circularity but you can't just use the first cons cell as a marker, because you will be looping forever inside the sublist that is circular. This is the kind or problems the Tortoise and Hare algorithm solves (there might be other techniques, the most common being storing visited elements in a hash table).

---

After your last edit, here is what I would do if I wanted to check for circularity, in a recursive fashion, without labels:

(defun circularp (list &optional seen)
  (and (consp list)
       (or (if (member list seen) t nil)
           (circularp (cdr list) (cons list seen)))))

We keep track of all the visited cons cells in seen, which is optional and initialized to NIL (you could pass another value, but that can be seen as a feature).

Then, we say that a list is circular with respect to seen if it is a cons cell which either: (i) already exists in seen, or (ii) is such that its CDR is circular with respect to (cons list seen).

The only additional trick here is to ensure the result is a boolean, and not the return value of member (which is the sublist where the element being searched for is the first element): if your environment has *PRINT-CIRCLE* set to NIL and the list is actually circular, you don't want it to try printing the result.

Instead of (if (member list seen) t nil), you could also use:

• (when (member list seen))
• (position list seen)
• and of course (not (not (member list seen)))