schemeに括弧を正しく貼り付けるにはどうすればいいですか？

Question

私が行うとき、私は理由を理解していない：

(cons (list 1 2) (list 3 4)) 

は、私はそれは三元ツリーだ

((1 2) 3 4) , but not a ((1 2) (3 4)) 

または

  .__4 
     /\ 
     . 3 
    /\ 
    1 2` 

を取得します。左の子 - 2つの葉を持つバイナリツリー。中と右の子供はちょうど葉。

私は((1 2) (3 4))と2つの子（それぞれがそのバイナリツリー）を持つバイナリツリーを持っているとします。

なぜ、SICP (page 103)の著者は、バイナリツリーではなく、3値ツリーが画像を描画するのですか？

Answer 1

のは、この変換を使用してみましょう：

(cons a b) = /\   and empty = . 
       a b 

まず、我々は二つのリストがあります：二つのリストに

consを使用して

(list 1 2) = (cons 1 (cons 2 empty)) = /\ 
             1 /\ 
              2 . 

(list 3 4) = (cons 3 (cons 4 empty)) = /\ 
             3 /\ 
              4 . 

が与える：

リストを使用して

(cons (list 1 2) (list 3 4)) = (cons (cons 1 (cons 2 empty)) 
            (cons 3 (cons 4 empty))) 
          = /\ 
           /\ /\ 
           1 /\ 3 /\ 
            2 . 4 . 

を与える：

(list (list 1 2) (list 3 4)) = (cons (cons 1 (cons 2 empty)) 
            (cons (cons 3 (cons 4 empty)) 
              empty 
          =  /\___ 
           /\  /\ 
           1 /\ /\ . 
            2 . 3/\ 
             4 . 

SICPの108ページでは、ツリーのリストとして表されるツリーがあると想定しています。 これは、consがツリーの作成に使用されていないと仮定しています。

彼らは翻訳を使用します。

empty = . 

(list a) = | 
      a 

(list a b) = /\ 
      a b 

(list a b c) = /|\ 
       abc 

彼らの例

(list (list 1 2) 3 4) = /|\ 
          /\3 4 
          1 2 

空のリストが例ではありませんでしたので、私たちが使用していません。図の中にある。

簡潔に：consとemptyで構築された一般的なデータ構造を描くのにSICPの表記法を使用することはできません。

Answer 2

リストを構築するために使用される、(cons x y)は、その残りの要素として（リストであることを結果ためのリストでなければならない）、その最初の要素とyとして（任意の型であり得る）xを有するリストを作成します。したがって、(cons 1 (list 3 4))は(1 3 4)、(cons (list 1 2) (list 3 4))の場合は((1 2) (3 4))となります。(1 2)がリストの最初の要素にすぎないためです。

結果を((1 2) (3 4))にしたい場合は、consの代わりに(list (list 1 2) (list 3 4))と書いてください。

SICPが3値ツリーを描画するのは、各リストが各要素が子であるノードを表すように、ツリーを表すことです。したがって、3つの要素（例えば、(1 2 (3 4))）を持つリストは、2つの葉と2つの子（両方の葉）を持つ1つのサブツリーという3つの子を持つノードです。