1

Scheme で 2 つのリストの構造上の等価性を確認するにはどうすればよいですか? たとえば、(a (b) (c d))は と等しく(a b (c d) (e f g))、(a b)は と等しくなり(a b c)ます。リストのデータ内容は重要ではなく、ネストされたリストの構造階層、つまりサブリストの数、およびそれらのサブリストのサブリストの数などのみが重要です。

eqStruct2 つのリストを引数として受け取る関数を作成しました。各リスト内のサブリストの数をカウントし、ブール値を返すことになっaてbいます。関数は list の各要素を調べa、次にlist の各要素を調べますb。およびそれぞれのサブリスト数のカウンタとしてcおよびを使用し、これらは、リストの要素で呼び出されたときに false を返すとインクリメントされます。リストの最初のアトムが見られるたびに、リストは最初の項目 (list-tail) なしでそれ自体に等しくなるように設定され、リスト 'a および 'b 全体が見られるとループが終了します。dabatom?unless

(define (eqStruct 'a 'b)

    (define c 0)
    (define d 0)

    (define (atom? x) (not (pair? x)))

    (unless (null? a)
         (unless (atom? (first a)) (set! c (+ c 1))
         (set! a (list-tail a 1))
    )
    (unless (null? b)
         (unless (atom? (first b)) (set! d (+ d 1))
         (set! b (list-tail b 1))
    )

    (eq? c d)
)

関数を述語にして、リストの構造が等しいかどうか、ブール値を返すようにしたいので、最後の行は一種の return ステートメントになるはずですが、それを実現する方法がわかりませんでした。この問題についても正しい方法で考えていました。

4

1 に答える 1

4

あなたのアプローチ

あなたのコード (およびそれに関するコメント) は、特定の Racket 構造に関するいくつかの誤解を示しています。

大きな問題はunless、ループ構造ではないことです。条件付きでコードを実行するだけです。たとえば、 を評価(unless (= 1 2) (display 'x))した場合、永久に印刷するのではなくx、一度印刷するだけです。これは、取得したコードが期待どおりに動作しないことを意味します。

ただし、(コードが何をしようとしているのかを理解するために) そうであると仮定すると、合理的な考えが得られます。リストを反復して、リストaである要素の数を数えようとしています。

    (unless (null? a)
         (unless (atom? (first a)) (set! c (+ c 1))
         (set! a (list-tail a 1))
    )

リストが常に 1 層だけの深さになる場合、これは良い考えです。たとえば、((a b) c)and を((a) b c)正しくチェックしますが、 ((a (b)) c)(構造が正しい((())())) と(((a) (b)) c)(構造が((()())())正しいかどうかを確認したい場合は、リストである要素と同じ数の要素があるかどうかを確認したい場合 (aおよびはループ構造でした)、あなたは正しい軌道に乗っているでしょう。bunless

少し異なる (しかし似ている) アプローチ

各入力リストからリストの構造を表す値 (この場合は数値) を抽出し、それらの代表的な値を比較しようとする一般的なアプローチは適切です。わずかに異なる代表値を使用し、それらを少し異なる方法で比較する必要があると思います（eq?あなたの場合は問題ないと思いますが、私が念頭に置いている代表値には必要がありますequal?）。

それらが定義されている方法を考えると、構造体は と比較できることに注意してくださいequal?。その観察を踏まえると、おそらくこれを行う最も簡単な方法は、リストを受け取り、その正規構造を返すプロシージャを作成することだと思います。list?また、内部で を使用することにより、 の構造を持つifようなケースを適切に処理できることに注意してください。((a b) ())(() ())

(define (structure list)
  (if (null? list)
      list
      (if (list? (car list))
          (cons (structure (car list)) (structure (cdr list)))
          (structure (cdr list)))))

> (structure '(a (b) (c d)))
(() ())
> (structure '((a b) ()))
(() ())

次に、2 つのリストの構造を比較するには、2 つのリストの構造を取得して比較します。

(define (structure-equal? list1 list2)
  (equal? (structure list1)
          (structure list2)))

> (structure-equal? '(a b) '(a b c))
#t
> (structure-equal? '(a (b) (c d)) '(a b (c d) (e f g)))
#t

構造上でどのように機能するかを理解するequal?ことはそれほど難しいことではありませんが、どのよう structureに機能するかを理解することはより重要です。もっと詳しく見てみましょう

(define (structure list)
  (if (null? list)
      list ; or '()
      (if (list? (car list))                                    
          (cons (structure (car list)) (structure (cdr list)))
          (structure (cdr list)))))

list入ってくる は、実際にはリストであると想定しています。これは、それが空のリストであるか()(そうです)、またはと(null? list)を持つペアであることを意味します。空のリストの構造は明らかに空のリストであるため、そのまま返すことができます(空なので)。もう 1 つのケースはより複雑です。 ある値と残りのリストのペアです。もリストである場合、の構造に何かが追加されますが、そうでない場合、それは単なる要素であり、リストの構造には寄与しません。より具体的には、ペアはいつですか：carcdrlistlistcarcdrcarlistlist(x . y)

  • xがリストの場合、の構造(x . y)は(<structure of x> . <structure of y>)
  • xがリストでない場合、 の構造は(x . y)です<structure of y>。

これにより、インナー内のロジックが説明されるはずですif(とのペアを作成します(a . b)) (cons a b)。

于 2013-10-15T23:03:37.340 に答える