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

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

Итак, нам задано выражение (list 1 (list 2 (list 3 4))).

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

(1 (2 (3 4)))

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

2241.png

а список (1 2) изображается так:

2242.png

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

2243.png

Интерпретация в виде дерева выглядит таким образом:

2244.png

Если присмотреться, можно заметить определенное сходство между лесенкой стрелочной диаграммы и деревом.

Write a comment