list - 过滤器列表 (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

长话短说?- tfilter(\bar(_,S)^(S=12), Xs, Ys).

---

现在，一步一步:

您的程序有几个问题。最大的是实际的问题陈述，它留下了几件事情。例如，我假设您希望所有元素都采用 bar(X, N) 形式，并且您希望选择具有 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 = [].

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

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

陈述积极的选择标准。

让我们为选择标准使用一个单独的谓词，并将其命名为 _true:

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

说明否定选择标准。

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).

所以我们得到两个答案:一个选择元素 X provided 它的形式是 bar(_,12)。而另一个，它不选择元素，但确保第二个元素不是 12。

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

将标准合并为一个“具体化”的定义

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)。