Common Lispの線形再帰リスト差分関数

Question

こちら楽しみのためのチュートリアル、そして彼が言う最後のこと、「運動：結合と差分の線形再帰的実装を与える」にこだわった。 （リスト用）

組合、汗なし。

違い、汗。

試行は次のようになります。 。 。

(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))
  )
)

今では、L2にないL1にあるすべての要素を返しますが、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))
  )
)

Answer 1

差を設定操作L1 \ L2は、eがL1だが、L2にはない。したがって、2回目の試行が実際に正しいように見えます：

  

同様に、L2をインラインで変更すると   3を「nil」にすると、すべてを返します   L2にはないL1のうち、どれも   L2。

対称差を計算しようとしているようですが、そうではありませんこれがエクササイズが要求するものであることは私には明らかです。

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

Answer 2

Lispでは、これは「差の設定」の定義です：

set-difference list1 list2 &key (test #'eql) test-not (key #'identity)
   Function
   Returns a list of elements of list1 that do not appear in list2. 

それは修正した実装です：

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