Prolog - 如何检查列表是否包含特定元素？

Question

我第一次尝试使用Prolog并在使用列表方面遇到了一些困难。

假设我有一个元素列表，我想要检查该列表是否具有以下元素：

所有的：A1、A2、A3、A4、A5

其中之一：B1、B2、B3、B4

其中两个：C1、C2、C3、C4、C5、C6

例如，[A1, A2, B2, C1, A3, A4, C4, A5] 满足要求，而[A2, A1, C1, B1, A3, A4] 不满足要求。

如何编写代码来判断一个列表是否符合上述要求，如果符合返回“Yes/True”，否则返回“No/False”？类似地，如何编写代码查找列表中缺失的元素以符合上述要求？

- sanNg

Answer 1

您问了很多问题！让我来为您提供一些谓词，解决大部分需求。

首先，我们来解决检查一个列表中的所有条目是否也在另一个列表中的情况：

subset([ ],_).
subset([H|T],List) :-
    member(H,List),
    subset(T,List).

这种简单的递归利用熟悉的 member/2 谓词来验证第一个参数指定的列表中的每个条目是否也在第二个参数指定的列表中。 [为简单起见，我假设这些列表的条目是不同的。如果我们想要验证第一个列表的多个实例匹配至少与第二个列表中的那么多实例，则需要更详细的版本。]

好的，那么如何检查第一个列表中至少有一个条目也属于第二个列表？显然，这是与上述谓词不同的谓词。 目标不是第一个列表中的所有项目，而是如果第一个列表中存在任何一个项目属于第二个列表，则满足目标。

intersects([H|_],List) :-
    member(H,List),
    !.
intersects([_|T],List) :-
    intersects(T,List).

如果第一个参数到达空列表，则此递归将失败，但如果在此之前找到属于第二个列表的第一个列表成员，则递归将成功。[即使在任一列表中出现项目的多个实例，此谓词也能正常工作。但是，如果我们想要检查第一个列表中的恰好一个项目是否属于第二个列表，那么我们需要完善逻辑，并且需要考虑多个实例与一个精确计数的一致性或相悖性。]

如果我们想要概括这个检查，以验证第一个列表中（至少）N个项目是否在第二个列表中，那么生成的谓词将需要第三个参数：

intersectsAtLeast(_,_,N) :- N <= 0, !.
intersectsAtLeast([H|T],L,N) :-
    member(H,L),
    !,
    M is N-1,
    intersectsAtLeast(T,L,M).
intersectsAtLeast([_|T],L,N) :-
    intersectsAtLeast(T,L,N).

这个递归函数通过遍历列表，每当第一个列表中的一个项也在第二个列表中时，就将第三个参数减1，并在计数减少到0（或以下）时成功。[如果列表可能具有重复项，则此处的代码需要更多工作。]

最后，你询问如何编写“返回缺失值”的内容以满足要求。在检查两个列表中的一个或多个项时，“缺失值”可能是许多可能项中的任何一项，因此这并没有很好地定义。在我们要求第一个列表中的所有项都属于第二个列表的特殊情况下，可以确定“缺失值”（如果有的话）。

missingValues([ ],_,[ ]).
missingValues([H|T],L,K) :-
    member(H,L),
    !,
    missingValues(T,L,K).
missingValues([H|T],L,[H|K]) :-
    missingValues(T,L,K).

在这里，递归将项目从输入的第一个列表移动到输出的“缺失项目”第三个列表中，仅当它们不出现在第二个列表中时。

关于你的问题，最后需要注意符号。在Prolog中，变量是以大写字母或下划线开头的标识符，因此如果A1、A2等被视为“未知数”，而不是（正如我所认为的）不同的原子（常量），则会出现问题。改用小写字母可以解决这个问题。

- hardmath