(define x (list (list 1 2) (list 3 4)))

x

((1 2) (3 4))

(reverse x) ((3 4) (1 2))

(deep-reverse x)

((4 3) (2 1))

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

Напишите процедуру fringe, которая берет в качестве аргумента дерево (представленное в виде списка) и возвращает список, элементы которого - все листья дерева, упорядоченные слева направо. Например,

(define x (list (list 1 2) (list 3 4)))

(fringe x)

(1 2 3 4)

(fringe (list x x))

(1 2 3 4 1 2 3 4)

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

Бинарный мобиль состоит из двух ветвей, левой и правой. Каждая ветвь представляет собой стержень определенной длины, с которого свисает либо гирька, либо еще один бинарный мобиль. Мы можем представить бинарный мобиль в виде составных данных, соединив две ветви (например, с помощью list):

(define (make-mobile left right)

(list left right))

Ветвь составляется из длины length (которая должна быть числом) и структуры structure, которая может быть либо числом (представляющим простую гирьку), либо еще одним мобилем:

(define (make-branch length structure) (list length structure))

a.Напишите соответствующие селекторы left-branch и right-branch, которые возвращают левую и правую ветви мобиля, а также branch-length и branch-structure, которые возвращают компоненты ветви.

b.С помощью этих селекторов напишите процедуру total-weight, которая возвращает общий вес мобиля.

c.Говорят, что мобиль сбалансирован, если момент вращения, действующий на его левую ветвь, равен моменту вращения, действующему на правую ветвь (то есть длина левого стержня, умноженная на вес груза, свисающего с него, равна соответствующему произведению для правой стороны), и если все подмобили, свисающие с его ветвей, также сбалансированы. Напишите предикат, который проверяет мобили на сбалансированность.

d.Допустим, мы изменили представление мобилей, так что конструкторы теперь приняли такой вид:

(define (make-mobile left right) (cons left right))

(define (make-branch length structure) (cons length structure))

Как много Вам нужно изменить в программах, чтобы перейти на новое представление?

Отображение деревьев

Точно так же, как map является мощной абстракцией для работы с последовательностями, map, совмещенная с рекурсией, является мощной абстракцией для работы с деревьями. Например, процедура scale-tree, аналогичная процедуре scale-list из раздела 2.2.1, принимает в качестве аргумента числовой множитель и дерево, листьями которого являются числа. Она возвращает дерево той же формы, где каждое число умножено на множитель. Рекурсивная схема scale-tree похожа на схему count-leaves:

(define (scale-tree tree factor) (cond ((null? tree) nil)

((not (pair? tree)) (* tree factor)) (else (cons (scale-tree (car tree) factor)

(scale-tree (cdr tree) factor)))))

(scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7))

10)

(10 (20 (30 40) 50) (60 70))

Другой способ реализации scale-tree состоит в том, чтобы рассматривать дерево как последовательность поддеревьев и использовать map. Мы отображаем последовательность, масштабируя по очереди каждое поддерево, и возвращаем список результатов. В базовом случае, когда дерево является листом, мы просто умножаем:

(define (scale-tree tree factor) (map (lambda (sub-tree)

(if (pair? sub-tree)

(scale-tree sub-tree factor) (* sub-tree factor)))

tree))

Многие операции над деревьями могут быть реализованы с помощью подобного комбинирования операций над последовательностями и рекурсии.

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

Определите процедуру square-tree, подобную процедуре square-list из упражнения 2.21. А именно, square-tree должна вести себя следующим образом:

(square-tree

(list 1

(list 2 (list 3 4) 5)

(list 6 7)))

(1 (4 (9 16) 25) (36 49))

Определите square-tree как прямо (то есть без использования процедур высших порядков), так и с помощью map и рекурсии.

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

Абстрагируйте свой ответ на упражнение 2.30, получая процедуру tree-map, так, чтобы square-tree можно было определить следующим образом:

(define (square-tree tree) (tree-map square tree)) Упражнение 2.32.

Мы можем представить множество как список его различных элементов, а множество его подмножеств как список списков. Например, если множество равно (1 2 3) , то множество его подмножеств равно (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)). Закончите следующее определение процедуры, которая порождает множество подмножеств и дайте ясное объяснение, почему она работает:

(define (subsets s)

(if (null? s) (list nil)

(let ((rest (subsets (cdr s)))) (append rest (map {??) rest)))))

2.2.3 Последовательности как стандартные интерфейсы

При работе с составными данными мы подчеркивали, что абстракция позволяет нам проектировать программы, не увязая в деталях представления данных, и что она оставляет нам возможность экспериментировать с различными способами представления. В этом разделе мы представляем еще один мощный принцип проектирования для работы со структурами данных - использование стандартных интерфейсов (conventional interfaces).

В разделе 1.3 мы видели, как абстракции, реализованные в виде процедур высших порядков, способны выразить общие схемы программ, которые работают с числовыми данными. Наша способность формулировать подобные операции с составными данными существенным образом зависит от того, в каком стиле мы манипулируем своими структурами данных. Например, рассмотрим следующую процедуру, аналогичную count-leaves из раздела 2.2.2. Она принимает в качестве аргумента дерево и вычисляет сумму квадратов тех из его листьев, которые являются нечетными числами:

(define (sum-odd-squares tree) (cond ((null? tree) 0)

((not (pair? tree))

(if (odd? tree) (square tree) 0)) (else (+ (sum-odd-squares (car tree))

(sum-odd-squares (cdr tree))))))

При поверхностном взгляде кажется, что эта процедура очень сильно отличается от следующей, которая строит список всех четных чисел Фибоначчи Fib(k), где k меньше или равно данного целого числа n:

(define (even-fibs n) (define (next k) (if (> k n)