Prolog: Filtering a list?

Question

Hello! 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!

Answer 1

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), New = Temp;           //in case the filter outputs true, or the list 
    New = [A|Temp]).                     //plus the current element otherwise.

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

Answer 3

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