SICP Exercise 3.18

sicp

Question

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 cdr​s would go into an infinite loop. Exercise 3.13 constructed such lists.

Answer

This will probably work almost always, but if, for some reason, you have the string 'CYCLE_MARKER in your list, this would always return true.

(define (is-cycle? x)
  (cond ((not (pair? x)) #f)
        ((eq? 'CYCLE_MARKER (car x)) #t)
        (else (begin (set-car! x 'CYCLE_MARKER)
                     (is-cycle? (cdr x))))))

Testing it with one cycle and one regular list:

(define x (make-cycle (list 'a 'b 'c 'd)))
(define y (list 'a 'b 'c 'd))

(is-cycle? x)
(is-cycle? y)

Results:

#t
#f