list - 理解 SICP 中的树 - 练习 2.24

Question

来自 SICP

Exercise 2.24: Suppose we evaluate the expression (list 1 (list 2 (list 3 4))). Give the result printed by the interpreter, the corresponding box-and-pointer structure, and the interpretation of this as a tree (as in Figure 2.6).

问题是我的眼睛坏了，所以我既看不到盒子和指针图，也看不到图2.6。所以现在我只能猜测这个列表应该像树一样基于:

Another way to think of sequences whose elements are sequences is as trees. The elements of the sequence are the branches of the tree, and elements that are themselves sequences are subtrees.

请检查我的树解释。这只是我的想象。我非常有信心这是正确的，但无法确认，因为我找到的所有练习答案都是图片，我的屏幕阅读器无法阅读它们。

(list 1 (list 2 (list 3 4))) - 我认为这是树本身，或者根节点。这棵树有两个分支或 child 。
第一个分支 (1) 是叶节点，因此我们在树的这一侧完成。
第二个分支(list 2(list 3 4)是另一棵树。
现在我们关注子树(列表 2(列表 3 4)。它有两个 child /分支。
第一个分支是叶节点 (2)，所以我们到这里就完成了。
第二个分支是另一棵树(列表 3 4)。
现在我们关注子树(列表 3 4)。它有两个子分支。
它们都是叶节点，所以我们完成了。

这是正确的吗？我对这棵树的理解正确吗？

Answer 1

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 '())) '()));所以作为一个框指针结构，它实际上是 '(1 . ( (2 . (3 . ())) . () ))。它的car是1，它的cdr是盒子( (2 . (3 . ())) . () ) 其 cdr 是 () 及其 car - 盒子 (2 . (3 . ()));等等

在其最后一个框的 cdr 中带有 () 的列表被称为“正确列表”。任何其他的都被称为“不正确的列表”，例如

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