Prolog: Filtering a list?

Solution 1:

SWI-Prolog offers exclude/3 and other such meta-predicates. Your original problem can be coded like this:

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

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

Usage example:

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

Solution 2:

If you are searching for higher-order functions in Prolog, you should definetly consult Naish (1995), a very good resource on this.

His definition of filter/3 is the following (he uses difference-list notation, therefore escapes having to define filter/4):

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

I you have questions about this predicate, please ask me in the comment. Reading the paper is also highly recommended, it also definess map, foldr and compose! Note that many of the limitations he mentions (like, for example a missing call/3 or a higher-order apply do not apply anymore. SWI-Prolog has the =.. operator, which addresses all of his concerns and makes arbitrary n-order logic possible.

Solution 3:

There is an inherent problem with filter functions that take the success or failure of a predicate as criterion for filtering: The resulting program is no longer a pure monotonic program. It therefore loses all its declarative properties — the only meaning that remains is a procedural step-by-step interpretation. Here is a pure, reified version of filtering using 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).

The first argument is thus a closure/continuation that will receive two further arguments: The element and the resulting truth value.

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

Now, results remain precise:

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

There are four possibilities how a list of two elements can be filtered by the criterion of being equal to X. Each element might be equal or might be different.

The downside of this approach is that one has to provide reified versions of all criteria.