Prolog：如何过滤列表？

Question

我目前正在从事与Prolog相关的一个非常短暂的项目，但在尝试将我创建的“过滤器”应用于列表时遇到了困难。我已经准备好了你可以称之为过滤器，但是我无法应用它。最好我举个例子说明：

filter(A, B) 

如果满足特定条件，它将输出“true”。

filterList(A, [X, Y, Z])

...输出一个列表，其中包括第二个参数中所有使得过滤器输出false的元素。(因此如果filter(A,X)为真，则输出是[Y，Z])。

我已经准备好“filter”函数，但现在我需要将其应用于列表，如第二个示例所示，排除应用第一个参数时过滤器返回true的所有元素。

因此，如果过滤器是简单的A == B，则函数应该接收A [A，B，A，C，D，A]并输出[B，C，D]，显然已删除了适用过滤器的所有元素。

我在函数的基本结构上遇到了麻烦，所以如果有人能提供这样的函数的基本大纲，那将是非常有帮助的。我尽可能简化了我的情况，以便可以采取您可能提供的任何内容并根据我的需求进行修改。

先行致谢！

- Fireblend

Answer 1

SWI-Prolog提供了exclude/3和其他类似的元谓语。你原来的问题可以这样编码：

SWI-Prolog提供了exclude/3和类似的元谓词。您的原始问题可以这样编码：

are_identical(X, Y) :-
    X == Y.

filterList(A, In, Out) :-
    exclude(are_identical(A), In, Out).

用例示例：

?- filterList(A, [A, B, A, C, D, A], Out).
Out = [B, C, D].

- Kaarel

---

include(<(5), [3,4,5,6,7], As) 的作用与 filter(<(5), [3,4,5,6,7], As) 相同。 而 exclude 是其反义词，其结果与 filter(>=(5), [3,4,5,6,7], As) 相同。 - joeblog

可以不使用 are_identical 规则来完成。将 filterList 的 body 替换为 ---- exclude(=(A), In,Out)。 - DaveEdelstein

Answer 2

如果您正在寻找Prolog中的高阶函数，那么您应该一定参考Naish (1995)，这是一个非常好的关于此的资源。

他对filter/3的定义如下（他使用差分列表符号，因此避免了定义filter/4）：

filter(_,[],[]).
filter(P, A0-As0, As) :-
    (
        call(P, A0) -> As = A0-As1
    ;
        As = As1
    )
    , filter(P, As0, As1).

如果您对此谓词有疑问，请在评论中向我提问。强烈建议阅读论文，它还定义了map、foldr和compose！请注意，他提到的许多限制（例如缺少call/3或高阶apply）现在不再适用。SWI-Prolog具有=..运算符，可以解决他所有的问题，并使任意n阶逻辑成为可能。

- Aleksandar Dimitrov

---

Pitty Naish在他的结论中建议使用apply/3，但我猜现在流行的方法是使用call/n。apply/3就是call/3。 - user502187

请参阅以下讨论，了解为什么Naish参考资料存在争议：http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/naish.html - user502187

Answer 3

使用谓词的成功或失败作为过滤标准的过滤函数存在固有问题：结果程序不再是纯单调的程序。因此，它失去了所有声明性属性——唯一剩下的意义是一种逐步解释的过程。这里是使用 if_/3 的纯粹化版本的过滤：

tfilter(_CT_2,    [], []).
tfilter(CT_2, [E|Es], Fs0) :-
   if_(call(CT_2,E), Fs0 = [E|Fs], Fs0 = Fs ),
   tfilter(CT_2, Es, Fs).

因此，第一个参数是闭包/续体，将接收另外两个参数：元素和结果的真值。

=(X,X,true).
=(X,Y,false) :- dif(X,Y).

现在，结果保持精确：

?- tfilter(=(X),[A,B],Xs).
   X = A, B = X, Xs = [X,X]
;  X = A, Xs = [X], dif(X,B)
;  X = B, Xs = [X], dif(X,A)
;  Xs = [], dif(X,A), dif(X,B).

当筛选两个元素的列表时，有四种可能性，它们分别可以相等或者不相等于X。

这种方法的缺点是需要提供所有条件的具体版本。

- false

Answer 4

嗯，你们瞧，我刚刚解决了这个问题。所以，我提交了自己的答案，正如预料的那样，一个非常简短的函数就搞定了：

filterList(_,[],R,R).           % Returns answer when the list is exhausted.
filterList(L,[A|List],Temp,Res) :-
   filterList(L,List,New,Res),  % Recursive call, New is either the same list
   (  filter(L,A),              % in case the filter outputs true, or the list
      New = Temp
   ;  New = [A|Temp]            % plus the current element otherwise.
   ).

- Fireblend

---

这个版本对于任何列表都总是成功的。意图是什么？ - false

Answer 5

我获取一个国家的成年人 // Country = 国家, People = 人, Person = 单个人

habitants(USA, [juan, pedro, david])

adults(Adults, Country) :-
     findall(Person, (habitants(Country,People), member(People, Person), adult(Person)), Adults)

这是Prolog中的过滤器 // Asi es un filter en prolog

- Jesus Ledesma

Answer 6

filter(_,[],[]).
filter(Predicate,[First|Rest],[First|Tail]) :-
   filter(Predicate,Rest,Tail).
filter(Predicate,[_|Rest],Result) :-
   filter(Predicate,Rest,Result).

- Bill McEnaney

---

你觉得加入一些演示你提出的解决方案的样例查询怎么样？ - repeat