sicp exercise 3.18

; Exercise 3.18.  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 cdrs would go into an infinite loop. Exercise 3.13 constructed such lists.


(define (find-loop loop-list)
  (let ((seq '()))
    (define (traverse lst)
      (cond ((null? lst) #f)
            ((not (pair? lst)) #f)
            ((memq lst seq) #t)
            (else
              (let ((temp (list '())))
                (set-car! temp lst)
                (set-cdr! temp seq)
                (set! seq temp)
                (traverse (cdr lst))))))
    (traverse loop-list)))
         

(define part1 (list 1 2 3 4))
(define part2 (list 9 8 7 6))

; no loop till now
(display (find-loop part1))(newline)
(display (find-loop part2))(newline)

; join the two parts
(set-cdr! (last-pair part1) part2)
; make a loop
(set-cdr! (last-pair part2) part2)

(display part1) (newline)

(display (find-loop part1))(newline)
(display (find-loop part2))(newline)