Решение упражнения 2.25 из SICP

28 January, 2008 (20:24) | Решения упражнений

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

Итак, начнем с простого. Для списка (1 3 (5 7) 9) нам нужно сначала дважды выполнить cdr, чтобы получить ((5 7) 9), затем взять от результата car, получив (5 7), затем вновь cdr, получив (7), и, наконец, применить car и получить 7. При записи описанной послежовательности действий в виде выражения важно не забыть о том, что порядок следования операций в выражении будет обратным, так как операции префиксные. Получаем следующее:

(car (cdr (car (cdr (cdr ‘(1 3 (5 7) 9))))))

Здесь апостроф перед списком (1 3 (5 7) 9) означает, что список интерпретатор должен воспринимать список буквально как значение, а не пытаться вычислить его как выражение.

Теперь выделим семерку из списка ((7)). Для этого возьмем от него car, получив (7), а затем еще раз car, чтобы получить 7. В виде выражения получим:

(car (car ‘((7))))

Хочу сделать важное замечание. Операция car убирает внешние скобки у списка и возвращает первое значение. Операция cdr не убирает внешние скобки у списка, а убирает лишь его первое значение.

Это соображение пригодится нам для выделения семерки из списка (1 (2 (3 (4 (5 (6 7)))))). Сначала отбросим 1 с помощью cdr и получим ((2 (3 (4 (5 (6 7)))))). Обратите внимание на две скобки в начале. Теперь с помощью car отбросим внешние скобки, чтобы получить (2 (3 (4 (5 (6 7))))). Повторяя аналогично пару операций cdr с последующим car для отбрасывания 2, 3, 4, 5 и 6, получаем в итоге 7, что нам и было нужно. В виде выражения это выгляит так (довольно громоздко):

(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr ‘(1 (2 (3 (4 (5 (6 7))))))))))))))))))

Можно укоротить эту запись, используя составные операции вида cadr (группировка по две операции):

(cadr (cadr (cadr (cadr (cadr (cadr ‘(1 (2 (3 (4 (5 (6 7))))))))))))

или даже cadadr (группировка по четыре операции):

(cadadr (cadadr (cadadr ‘(1 (2 (3 (4 (5 (6 7))))))))).

Comments

Comment from thror
Date: February 10, 2008, 5:49 pm

Определенно, решение правильное, но не столь глубокое, как хотелось бы.

На самом деле, это упражнение, должно порождать у читателя одну из самых мощных абстракций работы с деревьями (мощнее даже, чем абстракция tree-map из последующего упражнения 2.30).

Назовем ее process-tree или обобщенная обработка дерева. Пусть задано дерево T с поддеревьями Tl и Tr (в действительности, в нашем случае это не совсем поддеревья в топологическом смысле, а Tl=car(T), Tr=cdr(T)).

Предположим мы обработали поддеревья Tl и Tr и получили ответы Rl и Rr. Таким образом, потребуется еще и функция F, комбинирующая результаты R=F(Rl,Rr).

Ну и наконец, когда в дереве мы достигаем листа m, то для его обработки потребуется “листовая” функция L. А если дерево T пустое, то положим результатом обработки N.

В результате, алгоритм обобщенной обработки дерева таков:
[1] Если T-пустое, вернуть N.
[2] Если Т-лист значение которого m, вернуть L(m).
[3] Иначе обработать левое поддерево, получив Rl, обработать правое поддерево, получив Rr. Вернуть F(Rl,Rr).

Вот как эту мысль можно выразить:

(define (process-tree combiner leaf null-value tree)
  (cond ((null? tree) null-value)
        ((not (pair? tree)) (leaf tree))
        (else (combiner (process-tree combiner leaf null-value (car tree))
                        (process-tree combiner leaf null-value (cdr tree))))))

На самом деле, я не ошибся, приведя этот комментарий здесь. В самый раз =) Вот как построить последовательности car’ов и cdr’ов, позволяющих получить доступ к листу со значением x в дереве tree:

(define (combine l x)
  (map (lambda (a) (append a (list x))) l))

(define (find-path tree x)
  (process-tree (lambda (l r) (append (combine l 'car) (combine r 'cdr)))
                (lambda (a) (if (= a x) '(()) '()))
                '()
                tree))

Собственно для этой цели она и была разработана изначально =). Ну а потом все остальное:

(define (scale-tree tree factor)
  (process-tree (lambda (l r) (cons l r))
                (lambda (x) (* x factor))
                '()
                tree))

(define (square-tree tree)
  (process-tree (lambda (l r) (cons l r))
                (lambda (x) (* x x))
                '()
                tree))

И даже абстракция tree-map попадает сюда очевидным способом:

(define (tree-map proc tree)
  (process-tree (lambda (l r) (cons l r))
                (lambda (x) (proc x))
                '()
                tree))

–thror

Comment from thror
Date: February 10, 2008, 5:52 pm

На самом деле, часто порядок обхода дерева важен, и следовало бы определить абстракции left-to-right-process-tree, right-to-left-process-tree. Но здесь это не столь уже важно.

–thror

Comment from Sergey Khenkin
Date: February 10, 2008, 11:14 pm

Классное замечание!
Очень красивый пример абстракции. На этом этапе может показаться сложноватым.
Разбираясь в реализации find-path через process-tree сделал свою реализацию (она практически идентична):

(define (find-path tree x)
    (process-tree (lambda (l r) (cond ((and (not l) (not r)) false)
                                      ((not r) (append l '(car)))
                                      (else (append r '(cdr)))))
                  (lambda (e) (if (= e x) '() false))
                  false
                  tree))

Comment from Sergey Khenkin
Date: February 10, 2008, 11:15 pm

thror,
спасибо за отличные комментарии.

Comment from thror
Date: February 11, 2008, 1:20 pm

Ну и еще одна реализация, которая чуть позже пришла на ум. Обратите внимание на определение функций xcar и xcdr, не выделяющих соответствующие части пары, а формирующие список их применений. Ответом будет список функций, выделяющих соответствующие листы, удовлетворяющие предикату.

(define (pick-leaves predicate tree)
  (define (xcar x)
    (list 'car x))

  (define (xcdr x)
    (list 'cdr x))

  (define (combine l f)
    (map (lambda (a) (lambda (x) (a (f x)))) l))

  (process-tree (lambda (l r) (append (combine l xcar) (combine r xcdr)))
                (lambda (a) (if (predicate a) (list (lambda (x) x)) '()))
                '()
                tree))

Обратите внимание на такое использование map, когда к объекту надо применить список функций, а не наоборот.

(define (pick n tree)
  (map (lambda (a) (a tree))
       (pick-leaves (lambda (x) (= x n)) tree)))

(pick 7 '(1 3 (5 7) 9))
(pick 7 '((7)))
(pick 7 '(1 (2 (3 (4 (5 (6 7)))))))

–thror

Comment from Максим
Date: November 27, 2014, 6:37 pm

Уважаемый thror, подскажите, что в вашем случае означают ‘car и ‘cdr?

Comment from Максим
Date: November 27, 2014, 8:50 pm

Для тех кто так же как я не понял объяснения thror из-за знака ‘ перед car и cdr:

(define a 1)
(define b 2)

(list a b) = (1 2)
(list a ‘b) = (1 b)
(list ‘a ‘b) = (a b)

Write a comment