Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Prolog: Filtering a list?

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!

like image 429
Sergio Morales Avatar asked Nov 18 '08 06:11

Sergio Morales


2 Answers

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].
like image 71
Kaarel Avatar answered Sep 19 '22 18:09

Kaarel


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.

like image 26
Aleksandar Dimitrov Avatar answered Sep 22 '22 18:09

Aleksandar Dimitrov