Exercise-3.18,3.19

Упражнение 3.18.

Напишите процедуру, которая рассматривает список и определяет, содержится ли в нем цикл, то есть, не войдет ли программа, которая попытается добраться до конца списка, продвигаясь по полям cdr, в бесконечный цикл.

Упражнение 3.19.

Переделайте упражнение 3.18, используя фиксированное количество памяти.

Вот эти решения, Первый вариант логическая модификация предыдущего упражнения, а второй реализация классического алгоритма.

Этот алгоритм заключается в том, что мы пускаем вперед быстрого бегуна и, если он настигнет медленного, то значит он пробежал по замкнутой траектории. Отдельно стоит заметить что данные решения работают только для структур где car любого элемента не является парой.

(define (circles? x)

  (define (contains? what where)

    (cond

      ((null? where) #f)

      ((eq? what (car where)) #t)

      (else (contains? what (cdr where)))))

  (let ((found '()))

    (define (helper x)

      (cond ((contains? x found) #t)

            ((not (pair? x)) #f)

            (else (begin

                    (set! found (cons x found))

                    (or (helper  (car x)) (helper  (cdr x)))))))

    (helper x)))

(define (cycle? x)

  (define (helper one-stepper two-stepper)

    (cond ((null? one-stepper) #f)

          ((null? two-stepper) #f)

          ((eq? one-stepper two-stepper) #t)

          (else (helper (cdr one-stepper) (cddr two-stepper)))))

  (if (or (null? x) (null? (cdr x)) (null? (cddr x))) #f (helper (cdr x) (cddr x))))