(define (contains-cycle? lst) 
   (let ((encountered (list))) 
     (define (loop lst) 
       (if (not (pair? lst)) 
           (if (memq lst encountered) 
               (begin (set! encountered (cons lst encountered)) 
                      (or (loop (car lst)) 
                          (loop (cdr lst))))))) 
     (loop lst))) 

I think the solution ablove is not correct eg:

     (define t1 (cons 'a 'b)) 
     (define t2 (cons t1 t1)) 

(cdr t2) ==> (a . b) (cdr (cdr (t2)) ==> b (contains-cycle? t2)==> #t

 (define (contains-cycle? x) 
   (define(inner return) 
      (let((C '())) 
        (define (loop lat) 
            ((not (pair? lat)) (return #f)) 
             (if (memq (car lat) C) 
                 (return #t) 
                   (set! C (cons (car lat) C)) 
                   (if(pair? (car lat)) 
                      ( or (contains-cycle? (car lat)) 
                           (loop (cdr lat))) 
                      (loop (cdr lat)))))))) 
        (loop x))) 
   (call/cc inner)) 

gws says: here is a simpler solution

 (define (cycle? x) 
   (define visited nil) 
   (define (iter x) 
     (set! visited (cons x visited)) 
     (cond ((null? (cdr x)) false) 
           ((memq (cdr x) visited) true) 
           (else (iter (cdr x))))) 
   (iter x)) 

Rptx: This last one is good. I would just add a clause to check if it is not a pair, to avoid an error on the cdr.

<< Previous exercise (3.17) | Index | Next exercise (3.19) >>


The solutions above all seem a little too complex. After looking at them I had to recheck the question a few times to make sure I'd not missed a requirement to use mutable data structures, but I don't see any such limitation.

 (define (has-cycle? l) 
   (define (detect pair countedList) 
     (cond ((not (pair? pair)) #f) 
           ((memq pair countedList) #t) 
           (else (detect (cdr pair) (cons pair countedList))))) 
   (detect l '()))