5
\$\begingroup\$

From SICP:

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

  1. I'm not sure how to fulfill this requirement so far.
\$\endgroup\$
5
  • \$\begingroup\$ Have you tried this on a cyclic list? I did, and it goes into an infinite loop. \$\endgroup\$
    – gcbenison
    Feb 7 '12 at 2:56
  • \$\begingroup\$ What list did you use? (define a... above makes a cyclic list and it returned ok for me. \$\endgroup\$
    – jaresty
    Feb 7 '12 at 12:10
  • \$\begingroup\$ Try it with a cyclic list where the cycle doesn't begin with the first element, i.e. (cons 'z a) where a is the same as in your example \$\endgroup\$
    – gcbenison
    Feb 7 '12 at 13:09
  • \$\begingroup\$ You're right - I'll need to think about this a bit to see if I can make it work. \$\endgroup\$
    – jaresty
    Feb 8 '12 at 14:32
  • \$\begingroup\$ Why not just replace the code on top with the updated code, leaving a note that the code is updated? Those who are then interested in seing the changes can see the edit history. \$\endgroup\$
    – ANeves
    Feb 8 '12 at 18:50
3
\$\begingroup\$

I can not express it in Lisp, but the idea is as follows:

use two pointers, at start point both to the list head. Then, increment one pointer by 1, and another by 2. If you detect two equal objects eventually, it means that list has a loop. In pseudo-code:

P0 = head;
P1 = head;
while(P0 != null and P1 != null) // Detect end of the list
  P0 = next(P0);
  P1 = next(next(P1));
  if ( *P0 == *P1 ) signal loop detected
end while

Of course, the list objects should be distinct and comparable, and next function must be correct.

Proof is not complicated. First, consider a case of "pure" loop when tail connected to head.

At step n (n'th iteration of the while loop in the code), P0 is at item (n mod N), and P1 is at item (2n mod N), which are equal if N is finite and n mod N == 0, or simply n = N

If the list has loop that starts somewhere inside, one can show that after some iterations the case will be reduced to the previous one.

Hope this helps. You can learn more about Cycle detection on Wikipedia.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.