理解scheme里的list與pair

(继续考古, 此为一年前写的备忘.)

首先,pair是最基礎的數據結構。

一個pair寫出來是點對的形式(a . b)，形象地表示如下：

 /\
a  b

其中取左邊的元素用car，取右邊的用cdr。

因此，(1 . (2 . (3 . ())))，可以表示為

 /\
1 /\
 2 /\
  3 ()

在scheme裏面可以簡寫為 (1 2 3)

而 (1 . (2 . 3) )，則可以劃爲

 /\
1 /\
 2  3

因此簡寫為(1 2.3)

注意 點 與元素之間必須用空格隔開，否則如果是數字就變成小數了。
對： (1 . 2)
錯： (1.2)

cons 用於生成一個新的pair，如下：

(cons '(1 2) '(3) ) => ((1 2) 3)
   / \
  /   \
 /\   /\
1 /\ 3 ()
 2 ()

(cons '(1) '(2 3) ) => ((1) 2 3)
   / \
  /   \
 /\   /\
1 () 2 /\
      3 ()

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

 /\
1 /\
 2 /\
  3 ()

可以理解為：生成一個pair，第一個元素直接copy，對第二個元素先去掉括號再copy過去。
也可以形象想為，把兩個參數分別作為左右子女掛到新的root上。

而list可以想像成把元素逐個作為左子女貼上去，如
(list 'a 'b '3 '4) => (a b 3 4)

 /\
a /\
 b /\
  3 /\
   4 ()