(define (square-list items) (define (iter things answer)

(if (null? things)

answer

(iter (cdr things) (cons answer

(square (car things))))))

(iter items nil)) И так программа тоже не работает. Объясните это.

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

Процедура for-each похожа на map. В качестве аргументов она принимает процедуру и список элементов. Однако вместо того, чтобы формировать список результатов, for-each просто применяет процедуру по очереди ко всем элементам слева направо. Результаты применения процедуры к аргументам не используются вообще - for-each применяют к процедурам, которые осуществляют какое-либо действие вроде печати. Например,

(for-each (lambda (x) (newline) (display x)) (list 57 321 88))

57 321

88

Значение, возвращаемое вызовом for-each (оно в листинге не показано) может быть каким угодно, например истина. Напишите реализацию for-each.

2.2.2 Иерархические структуры

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

(cons (list 1 2) (list 3 4))

как список с тремя членами, первый из которых сам является списком. В сущности, это подсказывается формой, в которой результат печатается интерпретатором. Рисунок 2.5 показывает представление этой структуры в терминах пар.

Еще один способ думать о последовательностях последовательностей - деревья (trees). Элементы последовательности являются ветвями дерева, а элементы, которые сами по себе последовательности - поддеревьями. Рисунок 2.6 показывает структуру, изображенную на рис. 2.5, в виде дерева.

Естественным инструментом для работы с деревьями является рекурсия, поскольку часто можно свести операции над деревьями к операциям над их ветвями, которые сами сводятся к операциям над ветвями ветвей, и так далее, пока мы не достигнем листьев дерева. Например, сравним процедуру length из раздела 2.2.1 с процедурой count-leaves, которая подсчитывает число листьев дерева:

Глава 2. Построение абстракций с помощью данных (3 4)

((1 2) 3 4)

(1 2)

Рис. 2.5: Структура, формируемая (cons (list 1 2) (list 3 4))

((1 2) 3 4)

(1 2)

4

12

Рис. 2.6: Списковая структура с рис. 2.5, рассматриваемая как дерево.

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

(length x) 3

(count-leaves x) 4

(list x x)

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

2

(count-leaves (list x x)) 8

Чтобы реализовать count-leaves, вспомним рекурсивную схему вычисления length:

•Длина списка x есть 1 плюс длина cdr от x.

•Длина пустого списка есть 0.

Count-leaves очень похожа на эту схему. Значение для пустого списка остается тем же:

• Count-leaves от пустого списка равна 0.

3

4

1

2

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

•Count-leaves от дерева x есть count-leaves от (car x) плюс count-leaves от (cdr x) .

Наконец, вычисляя car-ы, мы достигаем листьев, так что нам требуется еще один базовый случай:

•Count-leaves от листа равна 1.

Писать рекурсивные процедуры над деревьями в Scheme помогает элементарный предикат pair?, который проверяет, является ли его аргумент парой. Вот процедура целиком:13

(define (count-leaves x)

(cond ((null? x) 0)

((not (pair? x)) 1)

(else (+ (count-leaves (car x))

(count-leaves (cdr x))))))

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

Предположим, мы вычисляем выражение (list 1 (list 2 (list 3 4))).Укажи-

те, какой результат напечатает интерпретатор, изобразите его в виде стрелочной диаграммы, а также его интерпретацию в виде дерева (как на рисунке 2.6).

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

Укажите комбинации car и cdr, которые извлекают 7 из следующих списков:

(1 3 (5 7) 9) ((7))

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

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

Допустим, мы определили x и y как два списка:

(define x (list 1 2 3)) (define y (list 4 5 6))

Какой результат напечатает интерпретатор в ответ на следующие выражения:

(append x y) (cons x y) (list x y)

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

Измените свою процедуру reverse из упражнения 2.18 так, чтобы получилась процедура deep-reverse, которая принимает список в качестве аргумента и возвращает в качестве значения список, где порядок элементов обратный и подсписки также обращены. Например:

13Порядок первых двух ветвей существен, поскольку пустой список удовлетворяет предикату null? и при этом не является парой.