Examine a list for cycles

From SICP:


Exercise 3.18. Write a procedure that
examines a list and determines whether
it contains a cycle, that is, whether
a program that tried to find the end
of the list by taking successive cdrs
would go into an infinite loop.
Exercise 3.13 constructed such lists.

I wrote the following (revised) solution:

(define (has-cycle? l)
  (define (rec nodes-visited remains)
    (define (leaf? node) (not (pair? node)))
    (define (have-seen? node)
      (define (rec rest)
        (if (null? rest) #f
             (or (eq? (car rest) node)
                 (rec (cdr rest)))))
      (rec nodes-visited))
    (cond
      ((leaf? remains) #f)
      ((have-seen? remains) #t)
      (else
       (or (rec (cons remains nodes-visited) (car remains))
           (rec (cons remains nodes-visited) (cdr remains))))))
  (rec '() l))

(define (last-pair x)
  (if (null? (cdr x))
      x
      (last-pair (cdr x))))

(define a '(a b c))
(has-cycle? a)
(set-car! (last-pair a) a)
a
(has-cycle? a)

(define b '(a b c))
(set-car! b (last-pair b))
b
(has-cycle? b)

(define c '(a b c d))

(set-car! (cddr c) (cdr c))
c
(has-cycle? c)

(define d (cons 'z a))
d
(has-cycle? d)

(define e '(a b c d e))
e
(has-cycle? e)

• How can it be improved?

Exercise 3.19. Redo exercise 3.18
using an algorithm that takes only a
constant amount of space. (This
requires a very clever idea.)

• I'm not sure how to fulfill this requirement so far.

I can not express it in Lisp, but the idea is as follows:

use two pointers, at start point both to the list head. Then, increment one pointer by 1, and another by 2. If you detect two equal objects eventually, it means that list has a loop. In pseudo-code:

P0 = head;
P1 = head;
while(P0 != null and P1 != null) // Detect end of the list
  P0 = next(P0);
  P1 = next(next(P1));
  if ( *P0 == *P1 ) signal loop detected
end while

Of course, the list objects should be distinct and comparable, and next function must be correct.

Proof is not complicated. First, consider a case of "pure" loop when tail connected to head.

At step n (n'th iteration of the while loop in the code), P0 is at item (n mod N), and P1 is at item (2n mod N), which are equal if N is finite and n mod N == 0, or simply n = N

If the list has loop that starts somewhere inside, one can show that after some iterations the case will be reduced to the previous one.

Hope this helps. You can learn more about Cycle detection on Wikipedia.

StackExchange Code Review Q#2499, answer score: 3