Prolog中的子列表（不包括空列表）

Question

我想在Prolog中创建一个谓词，以检查列表A是否是列表B的子列表。此外，我不希望我的程序将空列表视为另一个列表的子集。

例如：included_list([1,4],[1,2,3,4,5])应返回true。included_list([2,3],[1,2,3,4,5])应返回true。included_list([1,6],[1,2,3,4,5])应返回false。included_list([], [1,2,3,4,5])应返回false，并且如此等等...

因此，到目前为止，我已经编写了以下代码：

member(X,[X|Tail]).
member(X,[Head|Tail]):- member(X,Tail).

included_list([X],_).
included_list([Head|Tail],List):- member(Head,List), included_list(Tail,List).

但是上面的代码似乎是错误的，因为在某些情况下它会抛出true，而不是抛出wrong。我希望在呈现以下屏幕截图后能够清楚地表述：

正如您可能已经注意到的那样，第五(5)句话给出了true，而不是wrong。也就是说，当我写一个形如：

included_list([x,y],[w,x,v,z])。

其中只有x被包含在第二个列表中（而不是y），程序仍然返回true（这是错误的）。

通常，如果第一个列表的第一个参数被包含在第二个列表中，那么无论前者的其余部分是否被包含在后者中，该程序都会返回true。

在任何其他情况下，该程序将给出正确的结果(true或false)。

我做错了什么？

期待您的回答！

提前感谢您！

- Jimbo_ai

---

member/2是ISO标准，因此您无需自己定义它。而Prolog会抛出异常，而不是true或"wrong"。 - Daniel Lyons

首先，你的基本情况是有问题的！你说included_list/2对于任何一个单项列表都是成立的。相反，应该说included_list([], _)，这样就能正常工作了。 - Daniel Lyons

我倾向于使用forall(member(X, Subset), member(X, List))来解决它，但我非常烦恼它没有生成！ - Daniel Lyons

@DanielLyons 这就是 findall 的作用吗？forall 旨在用于副作用，它不创建绑定的事实是有意设计的。 - user1812457

@Boris 谢谢！另一方面，我在使用findall/3时遇到了困难。你知道怎么做吗？ - Daniel Lyons

@DanielLyons findall(X, ( member(X, Subset), member(X, List) ), Subset) 或者 foreach(member(X, Subset), member(X, List))。但我真的不会使用任何一个。 - user1812457

Answer 1

您的问题在于included_list/2的第一个条款。即：

included_list([X], _).

这是什么意思？它的意思是，“如果第一个参数是只有一个元素的列表，则成功，忽略第二个参数。”

顺便说一句：如果你不忽略编译器的警告，你早就会发现这个错误了。你应该会收到一个响亮而明确的“单例变量”警告，提示你所编写的代码并不是你想象中的那样。

实际上，你想要表达的更接近于：

subset_list([X|Xs], Ys) :-
    subset_list_1(Xs, X, Ys).

subset_list_1([], X, Ys) :-
    member(X, Ys).
subset_list_1([X|Xs], X0, Ys) :-
    member(X0, Ys),
    subset_list_1(Xs, X, Ys).

但我不知道为什么你不直接使用现有的subset/2，并要求子集不是一个空列表：

subset_list(Subset, List) :-
    Subset = [_|_], % a list with at least one element
    subset(Subset, List).

尽管文档中所述，subset/2的第二个参数并不一定是一个真正意义上的“集合”，但它要求两个列表都是ground（不包含任何自由变量）。您可以在这里查看源代码。

- user1812457

Answer 2

在这个回答中，我们使用元谓语 maplist/2处理递归，并定义：

all_included(Sub, Es)：
   same_length（Es，Xs），
   Sub = [_|_]，                     ％最小长度：1
   append（_，Sub，Xs），              ％最大长度：与“Es”一样长
   maplist（list_member（Es），Sub）。

让我们运行OP给出的查询！ 首先是我们预期成功的用例：

?- member(Xs, [[1,4],[2,3],[2,3,5],[3,4]]), all_included(Xs, [1,2,3,4,5]).
   Xs = [1,4]
;  Xs = [2,3]
;  Xs = [2,3,5]
;  Xs = [3,4]
;  false.

接下来，一些我们预计会失败的用例：

?- member(Xs, [[],[2,6],[1,6]]), all_included(Xs, [1,2,3,4,5]).
false.

?- all_included([3,5], [1,2,5]).
false.

- repeat