1

与えられた 2 つのリストの構造上の等価性をテストする Scheme 述語関数を作成します。2 つのリストは、リスト構造が同じであれば構造的に同等ですが、アトムは異なっていてもかまいません。

(123) (456) は問題ありません (1(23))((12)3) は問題ありません

これを行う方法がわかりません。どんな助けでも大歓迎です。

4

2 に答える 2

2

ここにいくつかのヒントがあります。これは、質問が宿題のように見えるため、少し繰り返して書く必要があります。詳細を記入してもらいます。

(define (structurally-equal l1 l2)
  (cond ( ? ; if both lists are null
         #t)
        ( ? ; if one of the lists is null but the other is not
         #f)
        ( ? ; if the `car` part of both lists is an atom
         (structurally-equal (cdr l1) (cdr l2)))
        ( ? ; if the `car` part of one of the lists is an atom but the other is not
         #f)
        (else
         (and (structurally-equal ? ?)     ; recur over the `car` of each list
              (structurally-equal ? ?))))) ; recur over the `cdr` of each list
于 2012-11-13T02:22:06.513 に答える
0

これには 2 つの方法があります。最初のものは、関数を使用して、リスト構造を表す出力を生成します。

  1. 任意のリストの構造を一意の文字列または数値として表現できる方法を考えてください。これにより、同一の構造を持つリストが同じ表現を持ち、他のリストが同じ出力を生成しないようになります。
  2. リストの構造を分析し、その出力を生成する関数を作成します。
  3. 関数を通して両方のリストを実行し、出力を比較します。同じなら同じ構造です。

2 つ目は、オスカーが取ったアプローチで、両方のリストを同時に繰り返すことです。ここでは、両方のリストを 1 つの関数に渡します。これは次のことを行います。

  1. 最初のリストの最初の要素は、2 番目のリストの最初の要素と (構造的に) 同一ですか? そうでない場合は、false を返します。
  2. これらは最初の要素リストですか? もしそうなら、の結果を返す(and (recur on the first element of both lists) (recur on the rest of both lists))
  3. そうでない場合は、の結果を返し(recur on the rest of both lists)ます。

2 番目の方法は、2 つのリストを比較する単純な状況ではより効率的です。違いが見つかるとすぐに返され、両方のリストが実際に構造的に同一である場合、両方のリストを完全に処理するだけで済みます。

リストの大規模なコレクションがあり、いつでも 2 つを比較したい場合は、最初のアプローチの方が効率的です。結果を保存できるため、どのリストも 1 回処理するだけで済みます。また、次のことができます。

  • たとえば、同じ構造を持つすべてのリストをグループ化するハッシュ マップを作成して、リストのコレクションを整理します。
  • 構造の類似性についてリストを比較します(例: これらのリストは、途中で異なる場合でも、同じ構造で開始および/または終了しますか?)

ただし、宿題は 2 番目の方法で行うのが最適であると思います。

于 2012-11-13T12:32:52.947 に答える