list Prolog - 如何检查列表是否包含某些元素？

Prolog - how to check if a list includes certain elements?

提问by sanNg

I am trying out Prolog for the first time and am having a little difficulty using lists.

我是第一次尝试 Prolog，但在使用列表时遇到了一些困难。

Say I have a list of elements. I want to check that the list has the following elements:

假设我有一个元素列表。我想检查列表是否包含以下元素：

All of: A1, A2, A3, A4, A5

全部：A1、A2、A3、A4、A5

One of: B1, B2, B3, B4

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

Two of: C1, C2, C3, C4, C5, C6

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

For example, [A1, A2, B2, C1, A3, A4, C4, A5] meets the requirements and [A2, A1, C1, B1, A3, A4] does not.

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

How would I got about writing something that returns Yes/True if a list meets the requirements and No/False otherwise? Similarly, how about writing something that returns the missing values from the list needed to meet the requirements?

如果列表满足要求，否则我将如何编写返回 Yes/True 的内容，否则我将如何编写返回 Yes/True 的内容？类似地，如何编写一些东西来返回满足要求所需的列表中的缺失值？

回答by hardmath

You asked a lot of questions! Let me get you started with some predicates that solve most of your requirements.

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

First let's tackle the case of checking that all entries of one list are also in the other list:

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

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

This simple recursion makes use of the familiar member/2predicate to verify each entry in the list specified by the first argument of subset/2is also in the list specified by the second argument. [For simplicity I've assumed that entries of these list are distinct. A more elaborate version would be needed if we wanted to verify multiple instances of an entry of the first list are matched to at least that many instances in the second list.]

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

Okay, how about a check that (at least) one of a first list belongs also to the second list? Obviously this is a different predicate than the one above. Instead of allitems in the first list, the goal is to be satisfied if there existsany one item in the first list that belongs to the second list.

好的，如何检查（至少）第一个列表中的一个也属于第二个列表？显然，这是一个不同于上面的谓词。而不是所有在第一列表中的项目，我们的目标是，如果有要满足存在于属于第二列表中的第一个列表中的任何一个项目。

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

This recursion failsif it reaches an empty list for the first argument, but succeeds if at any point before that a member of the first list is found that belongs to the second list. [This predicate would work fine even if multiple instances of an item occur in either list. However we'd need to refine the logic if we wanted check exactly oneitem of the first list belongs to the second list, and that would entail worrying about whether multiple instances are consistent with or counter to the exact count of one.]

如果它到达第一个参数的空列表，则此递归失败，但如果在此之前的任何时候找到属于第二个列表的第一个列表的成员，则该递归成功。[即使一个项目的多个实例出现在任一列表中，此谓词也能正常工作。但是，如果我们想要检查第一个列表中的一个项目是否属于第二个列表，我们需要改进逻辑，这将需要担心多个实例是否与一个的确切计数一致或相反。]

What if we want to generalize this check, to verify (at least) N items of the first list are in the second one? The resulting predicate will require a third argument:

如果我们想推广这个检查，来验证（至少）第一个列表的 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).

This recursion works through the list, decrementing the third argument by one each time an item on the first list turns out to be in the second list as well, and succeeding once the count is reduced to 0 (or less). [Again the code here needs more work if the lists can have repetitions.]

这种递归遍历列表，每次第一个列表中的项目也出现在第二个列表中时，将第三个参数递减一个，并在计数减少到 0（或更少）时成功。[如果列表可以重复，这里的代码需要更多的工作。]

Finally you ask about writing something that "returns the missing values" need to meet requirements. This is not well defined in the case of checking for one or more items on both lists, since a "missing value" might be any one of a number of possible items. In the special case where we asked for all the items on the first list to belong to the second list, the "missing values" can be determined (if any).

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

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

Here the recursion "moves" items from the input first list to the output "missing items" third list if and only if they do not appear in the second list.

当且仅当它们没有出现在第二个列表中时，递归将输入的第一个列表中的项目“移动”到输出的“丢失的项目”第三个列表。

One final note about your questions concerns notation. In Prolog variables are identifiers that start with a capital letter or an underscore, so the use of A1, A2, etc. as items on the list is heading for trouble if those are treated as "unknowns" rather than (as I assume you meant) distinct atoms (constants). Switching to lowercase letters would solve that.

关于您的问题的最后一个说明涉及符号。在 Prolog 中，变量是以大写字母或下划线开头的标识符，因此，如果将 A1、A2 等用作列表中的项目，如果它们被视为“未知”而不是（正如我假设您的意思），则会遇到麻烦) 不同的原子（常数）。切换到小写字母可以解决这个问题。