理解SICP樹 - 鍛鍊2.24

Question

從SICP

練習2.24：假設我們計算表達式（名單1（列表2（名單3 4）））。給出由解釋器打印的結果，相應的方框和指針結構，以及將其解釋爲樹（如圖2.6所示）。

問題是我的眼睛被破壞了，所以我既沒有看到盒子和指針圖，也沒有看到圖2.6。所以現在我只能猜測這個列表應該看起來像樹一樣：

另一種思考其元素是序列的序列的方法就像樹一樣。序列的元素是樹的分支，本身是序列的元素是子樹。

請檢查我的樹型解釋。這只是我的想象。我非常有信心這是正確的，但沒有辦法確認它，因爲我發現的練習的所有答案都是圖片，而我的屏幕閱讀器無法閱讀它們。

（list 1（list 2（list 3 4））） - 我認爲這是樹本身，或rootnode。這棵樹有兩個分支或孩子。
第一個分支（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)也有兩個分支 - 兩個葉子分支的樹和一個葉子分支。

作爲盒和指針結構，點象徵缺點細胞（即框），每一個與它的兩個插槽，或指針 - 的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))