2

私は楽しみのためにこのチュートリアルを進めていたのですが、彼が最後に言った「演習: 和と差の線形再帰的な実装を与えてください」という言葉に行き詰まってしまいました。（リスト用）

ユニオン、心配はいりません。

違い、汗。

試みはこのように見えます。. .

(defun list-diff (L1 L2)
  (cond
    ((null L1) L2) 
    ((null (member (first L1) L2)) (cons (first L1) (list-diff (rest L1) L2)))
    (t (list-diff (rest L1) L2))
  )
)

これで、L1 にあり、L2 にないすべての要素が返されますが、L2 のすべてが返されるだけです (明らかに)。同様に、3 行目の L2 を「nil」に変更すると、L2 にない L1 はすべて返されますが、L2 は返されません。

私の回避策の試みは再帰的ではないように見えます。再帰的であるときは、スタックオーバーフローが発生します ((list-diff L2 L1) をどこかで呼び出しようとした場合など)。

リスト交差などの彼の他の演習では、L1 の要素を実行するだけで済みます。ここで、L2 から重要な要素を取得するか、(list-diff L2 L1) を実行して、両方の結果を結合したいと考えていますが、これはもはや線形再帰的ではありません。

考え？

(実際には宿題ではありません。LISP を楽しみに見てみようと思っただけです。)

編集:応答に基づいて、これを適切に行う関数は次のとおりです。

(defun list-diff (L1 L2)
  (cond
    ((null L1) nil)
    ((null (member (first L1) L2)) (cons (first L1) (list-diff (rest L1) L2)))
    (t (list-diff (rest L1) L2))
  )
)
4

2 に答える 2

6

差分演算L1\L2は、eがL1にあるが、eがL2にないようなすべての要素eとして定義されます。したがって、2回目の試行は実際には正しいように見えます。

同様に、3行目のL2を「nil」に変更すると、L2にないL1はすべて返されますが、L2は返されません。

対称差を計算しようとしているように見えますが、これが演習で要求されていることであるかどうかは私にはわかりません。

それについて賢くしたい場合は、おそらく3番目のリストを関数に渡してアキュムレータとして機能させることができます。L1に要素がある場合、。のときに最初の要素をアキュムレータにプッシュします（そして再帰的に呼び出します）(null (member (first L1) L2))。L1がnullの場合、同じことを行って、L2の要素をアキュムレータリストと照合します。L1とL2がnullの場合、アキュムレータリストを返します。

于 2009-03-04T14:18:33.667 に答える