понимание дерева в SICP - упражнение 2.24

Question

От SICP

Упражнение 2.24: Предположим, мы оцениваем выражение (список 1 (список 2 (список 3 4))). Дайте результат, напечатанный интерпретатором, соответствующую структуру ящика и указателя и интерпретацию этого как дерева (как на рисунке 2.6).

Проблема заключается в том, что мои глаза уничтожены, поэтому я не вижу ни диаграммы, ни диаграммы указателей, ни диаграммы 2.6. Итак, теперь у меня есть только предположение, что этот список должен выглядеть как дерево на основе:

Другой способ думать о последовательностях, элементы которых являются последовательностями, - это деревья. Элементами последовательности являются ветви дерева, а сами элементы, которые являются последовательностями, являются поддеревьями.

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

(список 1 (список 2 (список 3 4))) - Я думаю, что это дерево или корневой каталог. Это дерево имеет две ветви или детей.
Первая ветвь (1) является листовым узлом, поэтому мы делаем это на этой стороне дерева.
Вторая ветка (список 2 (список 3 4)) - это еще одно дерево.
Теперь мы сосредоточимся на поддереве (список 2 (список 3 4)). Он имеет двух детей/ветвей.
Первая ветвь - 2), поэтому мы закончили здесь.
Вторая ветка - другое дерево (список 3 4).
Теперь мы сосредоточимся на поддереве (список 3 4). Он имеет две дочерние ветви.
Они оба являются листовыми , так что мы сделали.

правильно ли это? Разве я интерпретирую право дерева?

Answer 1

Ваша интерпретация верна. Результат, напечатанный интерпретатором, - (1 (2 (3 4))), то есть дерево, которое вы описали.

Answer 2

Настоящий примитив для создания списка в Lisp является cons. Список, который является результатом оценки формы (list 1 2 3), совпадает с результатом оценки (cons 1 (cons 2 (cons 3 '()))), а также может быть записан '(1 2 3 .()) или в его полностью пунктирной форме '(1 . (2 . (3 .()))).

Все они будут напечатаны в (1 2 3) интерпретатором:

(list 1 2 3)      '(1 2 3)    ; (1 2 3) 
(cons 1 (list 2 3))    '(1 . (2 3))   ; (1 2 3) 
(cons 1 (cons 2 (list 3)))   '(1 . (2 . (3)))  ; (1 2 3) 
(cons 1 (cons 2 (cons 3 '())))  '(1 . (2 . (3 .()))) ; (1 2 3) 

Рассматриваемые как дерево, (1 2 3) имеет три ветви - все листовые узлы: 1, 2 и 3. С другой стороны, , (1 (2 3)) имеет две ветви - лист и дерево из двух листовых узлов. И ((1 2) 3) также имеет две ветви - дерево из двух листовых ветвей и ветвь листа.

В качестве конструкции ящиков и указателей точки символизируют ячейки cons (т.е. коробки), каждая с двумя слотами или указатели - car (слева от точки) и cdr (справа от точка).

Таким образом, результат оценки (list 1 (list 2 3)), который напечатан как (1 (2 3)), также построен по вызову (cons 1 (cons (cons 2 (cons 3 '())) '())); так как структура box-and-pointer действительно '(1 . ((2 . (3 .())) .())). Его car - 1, а его cdr - ящик ((2 . (3 .())) .()), чье cdr - () и его car - коробка (2 . (3 .())); и т. д.

Списки с () в их последнем окне cdr известны как «надлежащие списки». Любые другие называются «неправильными списками», например.

'(1 2 . 3) 
= '(1 . (2 . 3)) 
= (cons 1 (cons 2 3))