Filter List (Prolog)

Question

My aim is writing a predicate filter/3. With input list [bar(a,12),bar(b,12),bar(c,13)] and filter criteria bar(A,12) the expected output is [bar(a,12),bar(b,12)].

The code below works but what is the difference between writing \+ \+ Filter = X and Filter = X (for me it is same). I wrote down the program by using 2 versions and it gave the same correct result. But I am sure that they are different?!

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

EDIT: @lurker you are right, they do not give the same result. ( it was my mistake)

----using \+ \+ Filter = X -----

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

----using 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

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

---

Now, step-by-step:

There are several issues with your program. The biggest is the actual problem statement which leaves several things open. For example, I assume that you expect that all elements are of the form bar(X, N) and you want to select those with N = 12. What you have implemented is slightly different:

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

This anomaly is due to your specific use of the cut. As you can see from the other answers, many versions avoid it. Cut is extremely difficult to use without any surprising effects. @CapelliC's version with cut actually avoids this one problem, but this is a very tricky business.

A further anomaly concerns the way how you might want to generalize your query. What about asking:

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

What should a correct answer be? Should Xs include X or not? After all, instances of this query produce different results, too! I will show two of them by adding the goals X = bar(a,12) and X = bar(a,13) in front.

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

So in one case we have an element, and in the other we have not. The general query should thus consequently produce two answers.

Here is an approach which does not have such problems:

State the positive selection criteria.

Let's use a separate predicate for the selection criteria, and call it _true:

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

State the negative selection criteria.

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

Now, with both, we can write a clean and correct filter program. Note that N is now just the second argument.

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

So we get two answers: One selecting the element X provided it is of the form bar(_,12). And the other one, which does not select the element, but ensures that the second element is not 12.

While these answers are all perfect and fine, I'm not very happy with it: It is correct but soo verbose. Here is a way to make it more compact.

Merge the criteria into one "reified" definition

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

There is a more compact and efficient way to express this using (=)/3

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

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

This (=)/3 can be more efficiently implemented as:

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

Now, we can use the generic tfilter/3:

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

And then, we can use library(lambda) to avoid the auxiliary definition:

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

Note that this (S = N) is not what you probably think! It is effectively not simple equality, but actually, the reified version of it! So it will be called like: call((S = 12), T) and thus =(S, 12, T).

Answer 2

The answer by @CapelliC answers your question.

There is another standard predicate, subsumes_term/2, which can be used to achieve the same effect as the double negation:

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

As to how to do the iteration over all elements, instead of a cut, prefer a conditional:

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

And if you write this, you can as well use include/3 (which, by the way, is literally a "filter" predicate):

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

Answer 3

Double negation it's an old 'trick of the trade' often used while writing metainterpreters.

Since variables instantiation due to unification it's undone on backtracking, it has a procedural only semantic of "prove a goal without binding its variables", whatever the meaning of such phrase could be.

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

If you comment out (i.e. remove) the double negation, you observe the undue instantiation effect: X has been bound to bar(a,12), and then cannot be matched to bar(b,12).

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

edit for the simple case at hand, an alternative implementation of filter/3 could be

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

or, better

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

but if your system implements subsumes_term/2, @Boris' answer is to be preferred