Exercise-3-21

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

Определите

процедуру print-queue, которая берет на входе очередь и выводит на печать последовательность

ее элементов.

Она могла бы выглядеть как-то так

(define (print-queue queue)
  (define (helper q)
    (if (not (null? q))
        (begin
          (display " " )
          (display (car q))
          (helper (cdr q)))))
    (display "(")
    (helper (front-ptr q))
    (display ")")
    (newline))

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

Exercise-3-17

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

Напишите правильную версию процедуры count-pairs из упражнения 3.16, которая возвращает

число различных пар в любой структуре.

Решение

(define (count-pairs x)

  (define (contains? what where)

    (cond

      ((null? where) #f)

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

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

  (let ((found '()))

    (define (helper x)

      (if (and (pair? x) (not (contains? x found)))

          (begin

            (set! found (cons x found))

            (+ 1 (helper  (car x)) (helper  (cdr x))))

          0))

    (helper x)))

Интересный прием заключен в конструкции

(set! found (cons x found))

В целом, весьма понятно что она делает, поэтому предлагается рассмотреть ее читателю самостоятельно.

Тест конструкции 

(define a (cons 1 2))

(define b (cons 3 a))

(define c (cons b a))

(set-cdr! a c)

(count-pairs c) ;3

Работает)

PS 2 упражнения с диаграммками пропущены.

Exercise-3.14

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

Следующая процедура, хотя и сложна для понимания, вполне может оказаться полезной:

(define (mystery x)

  (define (loop x y)

    (if (null? x)

        y

        (let ((temp (cdr x)))

          (set-cdr! x y)

          (loop temp x))))

Loop пользуется «временной» переменной temp, чтобы сохранить старое значение cdr пары x,

поскольку set-cdr! на следующей строке его разрушает. Объясните, что за задачу выполняет

mystery. Предположим, что переменная v определена выражением

(define v (list ’a ’b’c ’d).

 Нарисуйте диаграмму, которая изображает список, являющийся значением v. Допустим, что теперь мы выполняем (define w (mystery v)). Нарисуйте стрелочные диаграммы, которые показывают структуры v и w после вычисления этого выражения. Что будет напечатано в качестве значений v и w?

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

Exercise-3.13

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

Рассмотрим следующую процедуру make-cycle, которая пользуется last-pair из упражне-

ния 3.12:

(define (make-cycle x) (set-cdr! (last-pair x) x) x)

Нарисуйте стрелочную диаграмму, которая изображает структуру z, созданную таким кодом:

(define z (make-cycle (list ’a ’b ’c)))

Что случится, если мы попробуем вычислить (last-pair z)?

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

Exercise-3-12

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

В разделе 2.2.1 была введена следующая процедура для добавления одного списка к другому:

(define (append x y) (if (null? x) y (cons (car x) (append (cdr x) y))))

Append порождает новый список, по очереди наращивая элементы x в начало y. Процедура append! подобна append, но только она является не конструктором, а мутатором. Она склеивает списки вместе, изменяя последнюю пару x так, что ее cdr становится равным y. (Вызов append! с пустым x является ошибкой.)

(define (append! x y) (set-cdr! (last-pair x) y) x)

Здесь last-pair — процедура, которая возвращает последнюю пару своего аргумента:

(define (last-pair x) (if (null? (cdr x)) x (last-pair (cdr x))))

Рассмотрим последовательность действий

(define x (list ’a ’b))

(define y (list ’c ’d))

(define z (append x y))

z ;(a b c d)

(cdr x);b

(define w (append! x y));(a b c d)

w ;(a b c d)

(cdr x);(b c d)

В переменные z и w записываются “одинаковые” списки,но во втором случаем изначальный список также изменяется, чти и видно по выводу.

Interpriter

До этого момента я делал все упражнения, используя DrScheme и стандартный диалект racket, но работа с изменяемыми структурами тут отличается от предлагаемого синтаксиса в SICP, я нашел 2 выхода либо перейти на MIT Scheme либо выбрать язык R5RS. Второй вариант не интуитивен, но вроде рабочий, MIT Scheme оставим для любителей Emacs-a.