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!

Ciprian

Syntax: you can set a value to the &aux parameter directly: &aux (list2 list). – Nonproductive

an atom in the list is going to share the same address as the list itself a cons is not an atom. – Radmen

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

Radmen

I think that by "circular at its beginning" it means that it is linked back to its start, so tortoise may stay put, here; and hare may hop along slowly. :) – Whyalla

@WillNess Probably, but if it's circular but not back to the first cons a loop that naive would never terminate. – Radmen

Thank you, that was really helpful! I think I managed to implement the more naive solution, I will come back to the turtle and hare version though, because it is by far the most elegant. – Ciprian

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.

Nonproductive

Thank you (and for the syntax advice as well) ! After doing some testing, that does seem to be the case. I have read about the "turtle and hare" algorithm, although I'm not sure how I would implement it in lisp... Is there no way for the current function to be modified so that it moves forward along the list until it catches the circular reference? – Ciprian

@WillNess: Yes, I know? As I wrote: it can only catch one special case. To be explicit: '#1=(#1#). – Nonproductive