Wie können Klammern im Schema korrekt eingefügt werden?

Question

Ich verstehe nicht, warum, wenn ich tun:

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

ich

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

oder

  .__4 
     /\ 
     . 3 
    /\ 
    1 2` 

Es ist ein ternärer Baum ist. Linkes Kind - binärer Baum mit zwei Blättern. Mittleres und rechtes Kind ist nur ein Laub.

Ich nehme an, dass ich ((1 2) (3 4)) und Binärbaum mit zwei Kindern habe (jedes davon seine Binärstruktur)).

Warum also SICP (page 103) Autoren ein Bild zeichnen, wo ist ein ternärer Baum, kein binärer Baum?

Answer 1

Lassen Sie uns diese Übersetzung verwenden:

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

Zuerst haben wir die zwei Listen:

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

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

Mit cons auf den beiden Listen gibt:

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

Liste mit gibt:

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

In SICP Seite 108 nehmen sie an, dass wir einen Baum als Listen von Bäumen haben. Das heißt: Sie nehmen an, cons wurden nicht verwendet, um den Baum zu machen.

Sie nutzen die Übersetzung:

empty = . 

(list a) = | 
      a 

(list a b) = /\ 
      a b 

(list a b c) = /|\ 
       abc 

Ihr Beispiel

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

Da es keine leeren Listen im Beispiel waren wir nicht verwenden. in der Zeichnung.

Kurz gesagt: Die Notation in SICP kann nicht verwendet werden, um allgemeine Datenstrukturen zu zeichnen, die mit cons und empty erstellt wurden.

Answer 2

Wenn verwendet Listen zu erstellen, (cons x y) erstellt eine Liste, die x hat (die jede Art sein kann) als sein erstes Element und y (die eine Liste für das Ergebnis sein müssen, eine Liste zu sein) als seine übrigen Elemente. So (cons 1 (list 3 4)) gibt Ihnen (1 3 4) und (cons (list 1 2) (list 3 4)) gibt Ihnen ((1 2) (3 4)) weil (1 2) ist einfach das erste Element der Liste.

Wenn Sie möchten, dass das Ergebnis ((1 2) (3 4)) lautet, geben Sie (list (list 1 2) (list 3 4)) statt cons ein.

Der Grund dafür, dass SICP einen ternären Baum zeichnet, ist, dass er die Bäume darstellt, sodass jede Liste einen Knoten darstellt, bei dem jedes Element ein Kind ist. Eine Liste mit drei Elementen (zB (1 2 (3 4))) ist also ein Knoten mit drei Kindern: zwei Blätter und ein Unterbaum mit zwei Kindern (beide Blätter).