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？同样,如何编写从列表中返回缺失值的东西来满足要求？

Answer 1

你问了很多问题!让我开始介绍一些可以解决大部分需求的谓词.

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

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

这个简单的递归利用熟悉的member/2谓词来验证由subset/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等作为列表中的项目会遇到麻烦)不同的原子(常数).切换到小写字母可以解决这个问题.