あなたのコードはかなり奇妙だと思います。たとえば、あなたの 3 番目の節: 何のW
ために? 次のように言いたいようです。
difference([],[],_).
2 番目の問題: 4 番目の節では、H と D が同じ束縛を持つ独立変数であることを妨げるものは何もありません。次のような意味だと思います。
difference([H|T1],[D|T2],T3) :- H \= D, difference(T1,[D|T2],[H|T3]).
これらを修正すると、述語が修正され、合理的な見た目の答えが得られるようです。
| ?- difference([1,4,4], [1,4], R).
R = [4]
最初のいくつかの句は、さまざまな種類の基本ケースを処理しようとしていると思いますが、そうですか? 例えば:
difference(L, [], L) % handles the case where the second list is exhausted
difference([], _, []) % handles the case where the first list is exhausted
difference([], [], W) % handles the case where the lists are exhausted at the same time
これに関する 1 つの問題は、L = [] が正当なバインディングであるため、最初の節と 3 番目の節が同じことを意味することです。3 番目のものはおそらく安全に削除できます。これは、1 番目のものと一致して同じ答えを生成したからです。2 番目の節はより興味深いものです。これまでに行った作業に関係なく、最初のリストが空である場合、結果は空であると言っているように見えるからです。その可能性は少し耳障りだと思います。実際にこれら 2 つの基本ケースが必要な可能性はありますか? :
difference([], L, L).
difference(L, [], L).
私はまだ確信が持てませんが、あなたが何を達成しようとしているのかをよりよく理解するまで、私はこれ以上助けることができないかもしれません. たとえば、どうなるdifference([1, 4], [1, 4, 4], R)
でしょうか? おそらく必要だと思いR = [4]
ますが、コードは生成しR = []
ます。
また、その可能性は低いと思います
difference([],[],W):- write(X).
参照するものが何もないため、Prolog は X の新しい変数バインディングを生成するため、デバッグ戦略として役立ちます。
すべての変更を加えた最終バージョンは次のようになります。
difference(L, [], L) :- !.
difference([], L, L) :- !.
difference([H|T1], [D|T2], T3) :- D \= H, difference(T1, [D|T2], [H|T3]).
difference([H|T1], [H|T2], T3) :- difference(T1, T2, T3).
編集:これはあなたの要件を実装していますか?
not_in1(X, Left, Right) :- member(X, Left), \+ member(X, Right).
not_in(X, Left, Right) :- not_in1(X, Left, Right).
not_in(X, Left, Right) :- not_in1(X, Right, Left).
differences(Left, Right, Differences) :-
findall(X, not_in(X, Left, Right), Differences).
?- differences([1,2,3,4], [1,3,5], X).
X = [2,4,5]
もしそうなら、元のコードを取得して、一致する回答を生成しようとします。
編集2:OK、上記の解決策の問題は、それがO(N ^ 2)であることです。最悪の場合 (2 つの完全に異なるリスト)、リスト 1 のすべての項目をリスト 2 のすべての項目と比較する必要があります。両方のリストが順序付けられているという事実を利用していません (それが「縦」の意味だと思います)。
結果は元のコードにかなり似ていますが、元のコードは項目が順序付けられているという事実を利用していません。これが、4 番目と 5 番目のケースがわかりにくい理由です。どちらの数が大きいかに応じて、いずれかのリストまたは他方のリストを再帰する必要があります。修正されたコードは次のようになります。
differences([], Result, Result).
differences(Result, [], Result).
differences([H|Ls], [H|Rs], Result) :- differences(Ls, Rs, Result).
differences([L|Ls], [R|Rs], [L|Result]) :-
L < R,
differences(Ls, [R|Rs], Result).
differences([L|Ls], [R|Rs], [R|Result]) :-
L > R,
differences([L|Ls], Rs, Result).
これにより、O(N^2) メソッドと同じ結果が生成されることがわかります。
?- differences([1,2,3,4], [1,3,5], X).
X = [2,4,5]
あなたは正しかった、両方の基本ケースが必要です。これは、いずれかのリストの残りが結果の一部になるようにするためです。おそらく、これらは最大値になります([5]
例では)。
これで、3 つの帰納的なケースができました。1 つは<
、1 つは 、もう>
1 つは です=
。等式の場合は直感的です。両方のリストの先頭を破棄して、両方のリストで繰り返します。次のケースは、基本的に、左の頭が右の頭よりも小さい場合、それを結果に追加し、左の末尾に繰り返します。その場合、権利は変わりません。もう一方のケースは、このケースのミラーです。
お役に立てれば!