sicp-ex-3.18


  
 (define (contains-cycle? lst) 
   (let ((encountered (list))) 
     (define (loop lst) 
       (if (not (pair? lst)) 
           false 
           (if (memq lst encountered) 
               true 
               (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) 
          (cond 
            ((not (pair? lat)) (return #f)) 
            (else 
             (if (memq (car lat) C) 
                 (return #t) 
                 (begin 
                   (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)) 

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