Common Lisp - Writing a function that detects circular lists

Question

I have an assignment for my CS functional languages class where we must write a function able to detect whether or not a given list is circular at its beginning. The function has to be recursive. Let's name it circular :

* (setf list1 '(a b c d))
* (rplacd (cddr list1) list1)
* list1
#1=(A B C . #1#)
* (circular list1)
t
* (circular '(a b c a b c))
nil

Now, I know how to check for circularity in this case : at some point along the recursion, an atom a cons in the list is going to share the same address as the list itself, hence the circularity. Here is my function so far :

(defun circular (list &aux list2)
  (setf list2 list)
  (cond
    ((null list) nil)
    ((eq (car list) list2) t)
    (t (circular (cdr list))) ) )

I thought that by comparing the car of list against list2 at every point of the recursion the function would eventually return a result, but while the function does work for non-circular lists, it becomes infinitely recursive when I try to use it on a circular list. I am sure that I am missing something incredibly obvious here, but still, any help would be immensely appreciated!

Answer 1

This problem can be solved using the tortoise and hare algorithm where you have two cursors scanning though tortoise at one cons at a time and hare at double speed starting on the second element. If the tortoise and hare is the same element you have a cycle.

(defun cyclicp (list)
  "check if a list is cyclic using tortoise and hare algorithm"
  (loop :for tortoise on list
        :for hare on (cdr list) :by #'cddr
        :thereis (eq tortoise hare)))

So imagine you have the list, #1=(a b c . #1#) or more precisely '#1=(a . #2=(b . #3=(c . #1#))). It contains 3 cons with address 1,2,3 and each cons have one of symbolic value a, b, c.

If I write the car of the tortoise and hare you'll see the hare wraps around and eventually ends up at the same cons as tortoise

Iteration 1 2 3
Tortoise  a b c
Hare      b a c
              ^ match

Only thing you need to do is reimplement it using recursion. It would look something like this:

(defun cyclicp (list)
  "check if a list is cyclic using tortoise and hare algorithm"
  (labels ((aux (tortoise hare)
        (cond ((null hare) <??>)
              ((eq tortoise hare) <??>)
              (t (aux <??> <??>)))))
    (aux list (cdr list))))

EDIT

A naive and simpler version that only checks references back to the first cons can be done like this:

(defun cyclic-1-p (list)
  "check if a list is cycles back to the first cons"
  (loop :for cursor on (cdr list)
        :thereis (eq cursor list)))

Only thing you need to do is reimplement it using recursion. It would look something like this:

(defun cyclic-1-p (list)
  "check if a list is cycles back to the first cons"
  (labels ((aux (cursor)
        (cond ((null cursor) <??>)
              ((eq cursor list) <??>)
              (t (aux <??>)))))
    (aux (cdr list))))

If the cycle happens but not in the first cons this will not terminate.

(cyclic-1-p '(1 . #1=(2 3 . #1#))) ; never halts

Answer 2

You are throwing away the second value at each step. You are just comparing the list with its car everytime, so you can only catch one special case of circularity, where the list directly references itself.

What you need to do is try all circle lengths. The usual way for this is to have two references that move at different speeds through the list. You just need to prove that this will always terminate.

Update: Yes, that's the "turtle and hare" algorithm. You keep two references, which you update each loop: one advances by one, one by two steps. This way, the distance between the two references grows by one each step. As soon as both references have entered the circle (this may happen later in the list), you will have them coincide whenever that distance is a multiple of the circle length.