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.
I wrote the following (revised) solution:
(define (has-cycle? l) (define (rec nodes-visited remains) (define (leaf? node) (not (pair? node))) (define (have-seen? node) (define (rec rest) (if (null? rest) #f (or (eq? (car rest) node) (rec (cdr rest))))) (rec nodes-visited)) (cond ((leaf? remains) #f) ((have-seen? remains) #t) (else (or (rec (cons remains nodes-visited) (car remains)) (rec (cons remains nodes-visited) (cdr remains)))))) (rec '() l)) (define (last-pair x) (if (null? (cdr x)) x (last-pair (cdr x)))) (define a '(a b c)) (has-cycle? a) (set-car! (last-pair a) a) a (has-cycle? a) (define b '(a b c)) (set-car! b (last-pair b)) b (has-cycle? b) (define c '(a b c d)) (set-car! (cddr c) (cdr c)) c (has-cycle? c) (define d (cons 'z a)) d (has-cycle? d) (define e '(a b c d e)) e (has-cycle? e)
- How can it be improved?
Exercise 3.19. Redo exercise 3.18 using an algorithm that takes only a constant amount of space. (This requires a very clever idea.)
- I'm not sure how to fulfill this requirement so far.