0

私は、Scheme で 2 つのツリーが (データと構造において) 等しいかどうかをテストするコードを書いています。ノードごとに最大で 2 つの子しかないと仮定する必要があります。私のコードは次のとおりです。

(define (make-tree value left right) 
  (list value left right))
(define (value tree)
  (car tree))  
(define (left tree) 
  (car (cdr tree)))
(define (right tree)
  (car (cdr (cdr tree))))

(define (tree-equal? T1 T2)
 (if (and (null? T1) (null? T2)) 
   #t
   (if (= (value T1) (value T2))
      (tree-equal? (left T1) (left T2))
      (tree-equal? (right T1) (right T2)))))

(tree-equal? '(1 2 3) '(1 2 3))

私が得ている出力は車です：

 car: contract violation
 expected: pair?
 given: 2

誰かが私が間違っていることを説明できますか? (値 T1) でこのエラーが発生するのはなぜですか? 値関数を書き直して、ツリーが null かどうかを確認する必要がありますか?

4

1 に答える 1

4

エラーにつながる問題

carコードには、 , ではないものを呼び出すことになる可能性のある場所がいくつかあります(そのため、の引数は である必要があるというpair契約に違反します)。エラーメッセージが示すように、そのようなものの1つは. 特に、(はとの値であるため) を確認した後、次のようにツリーの左の枝に再帰します。carpair2(= 1 1)1(1 2 3)(1 3 2)

(tree-equal? (left T1) (left T2))

今、(left T1)を生成し2、 を(left T2)生成し3ます。どちらでもないので、とnullで次の行にたどり着きます。2 == T13 == T2

(= (value T1) (value T2))

valueは として定義されているためcar、 で呼び出そうとしていcarます2。

その他の問題…</h3>

それが解決された後も、比較関数にはまだいくつかの問題があり、その中には単純に文体的なものもあれば、実際に問題を引き起こすものもあります。

(define (tree-equal? T1 T2)                   
 (if (and (null? T1) (null? T2))              
   #t                                         
   (if (= (value T1) (value T2))              
      (tree-equal? (left T1) (left T2))       
      (tree-equal? (right T1) (right T2)))))

両方の木がである場合null?、それらが同じであることを確認するのは正しいです。一方がそうで、もう一方がそうでない場合はどうnull?なりますか? valueを呼び出して続行しますが()、これは良くありません。もう一方が ではnull?なく、リストでもない場合は、valueそれを呼び出してみますが、それも失敗します。2 つのツリーが得られ、たまたま同じ値を持っている場合は、それらの左側をチェックし、同じ値を持っていない場合は右側をチェックします。(これがどのように機能するかです。) 私は、それらが同じ値を持ち、同じ左をif持ち、同じ右を持っていることを本当に確認したいことを期待しています。

これは実際には、いくつかのブール ロジックを使用して単純化できます (右側のコメントが役立つはずです)。これは、tree?まだ定義していない述語を使用しますが、難しいことではなく、このコードをはるかに読みやすくします。

(define (tree-equal? T1 T2)                       ; T1 and T2 are tree-equal iff
  (or (eq? T1 T2)                                 ; 1. are the same (this covers both being null), OR
      (and (tree? T1) (tree? T2)                  ; 2. a. both are trees, AND
           (eq? (value T1) (value T2))            ;    b. values are eq, AND
           (tree-equal? (left T1) (left T2))      ;    c. lefts are tree-equal, AND
           (tree-equal? (right T1) (right T2))))) ;    d. rights are tree-equal

Lipsにおける「木」の伝統的な意味について

さて、あなたが各中間ノードに要素を持つバイナリ ツリーを使用していることは理解していますが、「ツリー」は Lisp コンテキストでコンス セル (つまり、ペア) から構築された任意の構造を示すためによく使用されることを指摘しておきます。 . 同じアプローチを使用してそれらを比較できますが、少しすっきりしています。

(define (tree-eq?  t1 t2)
  (or (eq? t1 t2)
      (and (pair? t1) (pair? t2)
           (tree-eq? (car t1) (car t2))
           (tree-eq? (cdr t1) (cdr t2)))))

ノードの1つがフォームを持っているため、この比較関数は、偶然にも、ツリーのタイプでも機能します。

(value . (left . (right . ())))

そのため、再帰呼び出しは、2 つのツリーからの値、左、および右を同時に処理することになります。もちろん、これは、(質問の意味で) 実際には合法的なツリーではない同等のツリー (伝統的な意味で) も認識します。tree?そのため、対応する関数を用意することが重要です (pair?従来のケースでは問題なく機能します)。

于 2013-10-15T20:22:42.567 に答える