过滤器列表 (Prolog)

Question

我的目标是写一个谓词filter/3。使用输入列表 [bar(a,12),bar(b,12),bar(c,13)] 和筛选条件 bar(A,12)，预期输出为 [bar(a,12),bar(b,12)]。

下面的代码有效，但是写 \+ \+ Filter = X 和 Filter = X 有什么区别（对我来说是一样的）。我使用 2 个版本写下了程序，它给出了相同的正确结果。但我确定它们是不同的？！

filter([],_,[]).
filter([X|XS],Filter,[X|ZS]) :-
   \+ \+ Filter=X,
   !,
   filter(XS,Filter,ZS).
filter([_|XS],Filter,ZS) :-
   filter(XS,Filter,ZS).

编辑： @lurker 你是对的，他们没有给出相同的结果。（这是我的错误）

----使用\+ \+ Filter = X -----

?- filter([foo(a,12),foo(c,12),foo(b,13)],foo(A,12),Res).
Res = [foo(a, 12), foo(c, 12)].

----使用Filter = X -----

?- filter([foo(a,12),foo(c,12),foo(b,13)],foo(A,12),Res).
A = a,
Res = [foo(a, 12)].

?- filter([foo(a,12),foo(a,12),foo(b,13)],foo(A,12),Res).
A = a,
Res = [foo(a, 12), foo(a, 12)].

Answer 1

双重否定是一个古老的 'trick of the trade' 经常在编写元解释器时使用。

由于变量实例化由于统一而在回溯时被撤消，因此它具有 "prove a goal without binding its variables" 的仅过程语义，无论此类短语的含义如何。

1 ?- filter([bar(a,12),bar(b,12),bar(c,13)],bar(_,12),L).
L = [bar(a, 12), bar(b, 12)].

如果您注释掉（即删除）双重否定，您会观察到不当的实例化效果：X 已绑定到 bar(a,12)，然后无法匹配到 bar(b,12) .

2 ?- filter([bar(a,12),bar(b,12),bar(c,13)],bar(_,12),L).
L = [bar(a, 12)].

edit 对于手头的简单案例，filter/3 的另一种实现可能是

filter([],_,[]).
filter([X|XS],Filter,ZS):- 
    X \= Filter, !, filter(XS, Filter, ZS).
filter([X|XS],Filter,[X|ZS]):- 
    filter(XS, Filter, ZS).

或者更好

filter([],_,[]).
filter([X|XS],Filter,R):- 
    (X \= Filter -> R = ZS ; R = [X|ZS]), filter(XS, Filter, ZS).

但是如果你的系统实现了subsumes_term/2，@Boris 的回答是首选

Answer 2

回答了您的问题。

还有一个标准谓词，subsumes_term/2，可以用来达到与双重否定相同的效果：

filter0([], _, []).
filter0([X|Xs], T, Ys) :-
    \+ subsumes_term(T, X),
    filter0(Xs, T, Ys).
filter0([X|Xs], T, [X|Ys]) :-
    subsumes_term(T, X),
    filter0(Xs, T, Ys).

关于如何对所有元素进行迭代，而不是切割，更喜欢有条件的：

filter1([], _, []).
filter1([X|Xs], T, R) :-
    (   subsumes_term(T, X)
    ->  R = [X|Ys]
    ;   R = Ys
    ),
    filter1(Xs, T, Ys).

如果你写这个，你也可以使用 include/3（顺便说一下，它实际上是一个 "filter" 谓词）：

filter(List, Term, Filtered) :-
    include(subsumes_term(Term), List, Filtered).

Answer 3

TL;DR ?- tfilter(\bar(_,S)^(S=12), Xs, Ys).

现在，一步一步：

你的程序有几个问题。最大的是实际的问题陈述，它留下了几件事情。例如，我假设您希望所有元素都采用 bar(X, N) 形式，并且希望 select 具有 N = 12 的元素。您实施的内容略有不同：

?- filter([bar(a,12),bar(b,12),bar(c,13)], bar(_,12), []).
true.

此异常是由于您对剪辑的特定使用。正如您从其他答案中看到的那样，许多版本都避免了它。如果没有任何令人惊讶的效果，Cut 极难使用。 @CapelliC 的 cut 版本实际上避免了这个问题，但这是一件非常棘手的事情。

另一个异常涉及您可能希望如何概括查询的方式。问什么：

  ?- filter([X], bar(_,12), Xs).

正确答案应该是什么？ Xs 是否应该包含 X？毕竟，此查询的 个实例 也会产生不同的结果！我将通过在前面添加目标 X = bar(a,12) 和 X = bar(a,13) 来展示其中两个。

 ?- X = bar(a,12), filter([X], bar(_,12), Xs).
 Xs = [bar(a,12)].

 ?- X = bar(a,13), filter([X], bar(_,12), Xs).
 Xs = [].

所以在一种情况下我们有一个元素，而在另一种情况下我们没有。因此，一般查询应该产生 两个答案。

这是一种没有此类问题的方法：

说明正 select 离子标准。

让我们为 selection 条件使用一个单独的谓词，并将其命名为 _true:

snd_bar_true(N, bar(_,N)).

说明负 select 离子标准。

snd_bar_false(N, bar(_,S)) :-
   dif(N, S).

现在，有了两者，我们可以编写一个干净且正确的过滤器程序。请注意 N 现在只是第二个参数。

filter([], _N, []).
filter([X|Xs], N, [X|Ys]) :-
   snd_bar_true(N, X),
   filter(Xs, N, Ys).
filter([X|Xs], N, Ys) :-
   snd_bar_false(N, X),
   filter(Xs, N, Ys). 

?- filter([X], 12, Xs).
   X = bar(_A, 12),
   Xs = [bar(_A, 12)]
;
   X = bar(_A, _B),
   Xs = [],
   dif(_B, 12).

所以我们得到两个答案：一个 select 元素 X 提供它的形式是 bar(_,12)。而另一个，它没有 select 元素，但确保第二个元素是 而不是 12.

虽然这些答案都很完美，但我不是很满意：它是正确的，但太冗长了。这是一种使它更紧凑的方法。

将标准合并为一个 "reified" 定义

snd_bar_t(N, bar(_,N), true).
snd_bar_t(N, bar(_,S), false) :-
   dif(S,N).

使用 (=)/3

有一种更紧凑、更有效的表达方式

snd_bar_t(N, bar(_,S), T) :-
   =(S, N, T).

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

这个 (=)/3 可以更有效地实现为：

=(X, Y, T) :-
   (  X == Y -> T = true
   ;  X \= Y -> T = false
   ;  T = true, X = Y
   ;  T = false,
      dif(X, Y)
   ).

现在，我们可以使用泛型 tfilter/3:

filter(Xs, N, Ys) :-
    tfilter(snd_bar_t(N), Xs, Ys).

然后，我们可以使用library(lambda)来避免辅助定义：

filter(Xs, N, Ys) :-
    tfilter(N+\bar(_,S)^(S = N), Xs, Ys).

请注意，这 (S = N) 可能不是您想象的那样！它实际上不是简单的相等，而是它的具体化版本！所以它会被称为：call((S = 12), T) 因此 =(S, 12, T).

过滤器列表 (Prolog)

Filter List (Prolog)

list

prolog

filter

将标准合并为一个 "reified" 定义