]> git.rkrishnan.org Git - sicp.git/blob - src/sicp/ex3_18.rkt
Solution to 4.44. A bit too verbose. Can be improved by better
[sicp.git] / src / sicp / ex3_18.rkt
1 #lang r5rs
2
3 #|
4 we use a unique hash and store them into a set. If we again hit an element
5 with the same hash, we have hit a cycle. For simplicity, we use car of a cell
6 as the hash. So for this procedure to work, we will need unique values in each
7 cell.
8 |#
9
10 (define (last-pair x)
11   (if (null? (cdr x))
12       x
13       (last-pair (cdr x))))
14
15 (define (make-cycle x)
16   (set-cdr! (last-pair x) x)
17   x)
18
19 (define z (make-cycle (list 'a 'b 'c)))
20
21 (define (cycle? x)
22   (define (contains-cycle? x trail)
23     (let ((f (car x))
24           (n (cdr x)))
25       (cond
26         ((not (pair? n)) #f)
27         ((memq f trail)  #t)
28         (else (contains-cycle? (cdr x) (cons f trail))))))
29   (contains-cycle? x '()))