list - 在 prolog 的 2 个列表中查找所有匹配元素

Question

我必须编写一个 Prolog 程序来查找 2 个单独列表之间的所有匹配元素。在实践中，它必须看起来像这样:

?- intersect([a,c,a,b], [d,b,a,b], X).

X = [a,b]

我目前的情况是这样的:

intersect([], Y, Z).
intersect([H| T1], Y, [H| T2]) :-
   member(H, Y),
   remove_all(H, T1, P),
   intersect(T1, Y, T2).
intersect([H| T1], Y, T2) :-
   intersect(T1, Y, T2).

(我必须在之前的练习中创建一个 remove_all 函数。这会从列表中删除与您提供的内容匹配的所有元素)

除了一件事，我的答案是这样的:

X = [a, b|_17660]

我是 Prolog 的新手，对此了解不多。为什么末尾有一个“|_17660”，我将如何更改我的代码来修复它？ 如果有人可以帮助我，我将不胜感激。

Answer 1

首先，您收到了三个关于“单例变量”的明确警告。这是一个非常明确的暗示，表明出了什么问题。通常，Prolog 程序员会首先解决这个问题。当然，还有其他方法。

所以你的问题是你得到 X = [a, b|_17660] 作为答案。这是什么意思？ _176660 只是一个变量名，必须通用量化。换句话说，你得到的答案是:

All X that start with [a, b|_] are a solution. Like [a, b] which is intended, but also ugly ones like [a, b|non_list]. Or even misleading or even incorrect ones like [a, b, c].

要了解此问题的根源，让我们关注隐含的地面查询，例如:

?- intersect([a,c,a,b], [d,b,a,b], [a,b|non_list]).
   existence_error(procedure,remove_all/3). % ERROR: Undefined procedure: remove_all/3

啊，你没有显示 remove_all/3 的定义。在传统的编程语言中，我们现在不得不停下来。但在 Prolog 中，我们仍然可以继续。不需要看那个定义。我将改为使用不再包含 remove_all/3 的specialization。所以从某种意义上说，这只是你程序的一部分，但是我们还是可以从中得出结论。这是我使用的:

intersect([], Y, Z) :- Z = non_list.
intersect([H| T1], Y, [H| T2]) :- false,
   member(H, Y),
   remove_all(H, T1, P),
   intersect(T1, Y, T2).
intersect([H| T1], Y, T2) :- T2 = non_list,
   intersect(T1, Y, T2).

This program is almost yours. Except that I have added extra goals to it. In another language this would not be possible. But in Prolog we can exploit a very nice property of (pure, monotonic) Prolog programs: You can add extra goals randomly and still predict what the outcome will be: The new program describes a subset of what your original program did. Of course, I had some suspicions, so my adding was somewhat guided. But you can always do the same with your buggy program!

Still not convinced? Now use that new program to see what you are actually describing:

?- intersect(Xs, Ys, Zs).
   Xs = [], Zs = non_list
;  ... .
?- intersect([], any, non_list).
   true.

显然，这不是您想要的。要查看它的来源，我们可以更加特化您的程序:

intersect([], Y, Z) :- Z = non_list.
intersect([H| T1], Y, [H| T2]) :- false,
   member(H, Y),
   remove_all(H, T1, P),
   intersect(T1, Y, T2).
intersect([H| T1], Y, T2) :- false,
   intersect(T1, Y, T2).

It should be evident by now, that the fact has to be specialized, otherwise these nonsensical solutions are possible. Here is such a specialization:

intersect([], _Y, Z) :-
   Z = [].
intersect([H| T1], Y, [H| T2]) :- false,
   member(H, Y),
   remove_all(H, T1, P),
   intersect(T1, Y, T2).
intersect([H| T1], Y, T2) :-
   intersect(T1, Y, T2).

The fact reads: The intersection of the empty list and anything is the empty list. Let's leave it that way, even if Y = non_list is now possible, too.

Your rule is still removed, since I have not seen your definition. It does not matter! I will continue to find problems in the remaining program. For the moment, I have no idea, where to look for problems. But I can ask Prolog to do this for me by asking the most general query which reads like

Prolog, just tell me all solutions you can describe.

(Remember this trick, you can always ask that question - without having even the slightest idea what the predicate is about.)

?- intersect(Xs, Ys, Zs).
   Xs = [], Zs = []
;  Xs = [_A], Zs = []
;  Xs = [_A,_B], Zs = []
;  ... .

第一个答案是完美的，但第二个答案不是。请注意，Ys 不会出现在任何地方，因此答案适用于所有 Ys。甚至:

?- intersect([a], [a], []).
   true.

这个问题与你的规则直接相关，没有任何条件......

参见 this一个干净的解决方案。