Prolog: Filtering a list?

Question

I'm currently working on a very short project on Prolog, and just got stuck trying to apply a "filter" I have created to a list. I have what you could call the filter ready, but I can't apply it. It'd be better if I illustrate:

filter(A, B) 

...outputs 'true' if certain conditions are met.

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

...outputs a list which includes all elements from the second argument that make the filter output false. (So if filter(A, X) is true, the output is [Y, Z] ).

I have the "filter" function ready, but now I need to apply it to a list as shown on the second example, excluding all elements for which the filter returns true when applied with the first argument.

So, if the filter is a simple A == B, the function is supposed to receive A [A,B,A,C,D,A] and output [B,C,D], having removed all the elements for which the filter applies, obviously.

I'm having trouble with the basic structure of the function, so if anyone could supply a basic outline for a function such as this it would be of great help. I've simplified my situation as much as possible so I can take whatever you may be able to provide and modify it for my needs.

Thanks in advance!

Zollie

Answer 1

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.

Rosalie

Pitty Naish proposes apply/3 in his conclusions, but I guess current way to go is to use call/n. apply/3 is simply call/3. – Cromagnon

See for a discussion why Naish Reference is disputed: complang.tuwien.ac.at/ulrich/Prolog-inedit/naish.html – Cromagnon

Answer 2

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

Joly

include(<(5), [3,4,5,6,7], As). works the same as filter(<(5), [3,4,5,6,7], As). exclude is the inverse in that it gives the same results as filter(>=(5), [3,4,5,6,7], As). – Ilyssa

can be done without the are_identical rule. replace filterList body with ---- exclude(=(A), In,Out) – Lithia

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

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.

Desman

Answer 4

Well what'd you know I just figured it out. So, here's me submitting an answer to my own question, as expected a really short function did the job:

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

Zollie

This version always succeeds for any list. Intended? – Desman

Answer 5

I get the adults of a country // Obtengo los adultos de un pais, Country = Pais, People = Personas, Person = una sola Persona

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

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

This is a filter in prolog // Asi es un filter en prolog

Townsend

Answer 6

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

Gesticulate

How about including some sample queries demonstrating your proposed solution in action? – Bedsore