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)) 

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) >>


AThird

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 '()))