src/sicp/ex3_18.rkt

   1 #lang r5rs
   2
   3 #|
   4 we use a unique hash and store them into a set. If we again hit an element
   5 with the same hash, we have hit a cycle. For simplicity, we use car of a cell
   6 as the hash. So for this procedure to work, we will need unique values in each
   7 cell.
   8 |#
   9
  10 (define (last-pair x)
  11   (if (null? (cdr x))
  12       x
  13       (last-pair (cdr x))))
  14
  15 (define (make-cycle x)
  16   (set-cdr! (last-pair x) x)
  17   x)
  18
  19 (define z (make-cycle (list 'a 'b 'c)))
  20
  21 (define (cycle? x)
  22   (define (contains-cycle? x trail)
  23     (let ((f (car x))
  24           (n (cdr x)))
  25       (cond
  26         ((not (pair? n)) #f)
  27         ((memq f trail)  #t)
  28         (else (contains-cycle? (cdr x) (cons f trail))))))
  29   (contains-cycle? x '()))