Filter list in prolog

Question

I'm trying to rewrite code from Haskell to Prolog.

count :: Eq a => a -> [a] -> Int
count x = length . filter (x==)

f :: [Integer] -> [Integer]
f [] = []
f list = filter (\x -> count x list == 1) list 

This code return list that contains elements that appears only once in the list. So if I have list [1,1,2,2,3,4,4,5] this function returns [3,5] I tried to find filter construction in Prolog but seems there no such thing. How can I make similar function in Prolog ?

Answer 1

To the existing answers, I would like to add an answer that is quite general in the sense that you can use it in multiple directions.

Building block: list_element_number/3

I start with the following predicate, defining a relation between:

• a list Ls0
• an element E
• the number N of occurrences of E in Ls0

Here it is:

list_element_number(Ls0, E, N) :-
        tfilter(=(E), Ls0, Ls),
        length(Ls, N).

This solution uses tfilter/3 from library(reif). The predicate subsumes the function count you have posted. The main benefit of this predicate over the function is that the predicate can be used not only in those cases that even Haskell can do easily, such as:

?- list_element_number([a,b,c], a, N).
N = 1.

No, we can use it also in other directions, such as:

?- list_element_number([a,b,c], X, 1).
X = a ;
X = b ;
X = c ;
false.

Or even:

?- list_element_number([a,b,E], X, 2).
E = X, X = a ;
E = X, X = b ;
false.

Or even:

?- list_element_number([A,B,C], X, 3).
A = B, B = C, C = X ;
false.

And even in the most general case, in which all arguments are fresh variables:

?- list_element_number(Ls, E, N).
Ls = [],
N = 0 ;
Ls = [E],
N = 1 ;
Ls = [E, E],
N = 2 ;
Ls = [E, E, E],
N = 3 .

We can fairly enumerate all answers like this:

?- length(Ls, _), list_element_number(Ls, E, N).
Ls = [],
N = 0 ;
Ls = [E],
N = 1 ;
Ls = [_160],
N = 0,
dif(E, _160) ;
Ls = [E, E],
N = 2 .

Main predicate: list_singletons/2

Using this building block, we can define list_singletons/2 as follows:

list_singletons(Ls, Singles) :-
        tfilter(count_one(Ls), Ls, Singles).

count_one(Ls, E, T) :-
        list_element_number(Ls, E, Num),
        cond_t(Num=1, true, T).

This uses cond_t/3 and (again) tfilter/3 from library(reif).

Sample queries

Here are a few sample queries. First, the test case you have posted:

?- list_singletons([1,1,2,2,3,4,4,5], Singles).
Singles = [3, 5].

It works as desired.

Now a case involving variables:

?- list_singletons([A,B], Singles).
A = B,
Singles = [] ;
Singles = [A, B],
dif(A, B).

On backtracking, all possibilities are generated: Either A = B holds, and in that case, there is no element that occurs only once. Or A is different from B, and in that case both A and B occur exactly once.

As a special case of the above query, we can post:

?- list_singletons([A,A], Singles).
Singles = [].

And as a generalization, we can post:

?- length(Ls, _), list_singletons(Ls, Singles).
Ls = Singles, Singles = [] ;
Ls = Singles, Singles = [_7216] ;
Ls = [_7216, _7216],
Singles = [] ;
Ls = Singles, Singles = [_7828, _7834],
dif(_7828, _7834) ;
Ls = [_7216, _7216, _7216],
Singles = [] ;
Ls = [_7910, _7910, _7922],
Singles = [_7922],
dif(_7910, _7922) .

Enjoy the generality of this relation, obtained via logical-purity.

Answer 2

A more simple version :

filter_list(L,OutList):-findall(X, (select(X,L, L1),\+member(X, L1)) , OutList).

?- filter_list([1,1,2,2,3,4,4,5],L).
L = [3, 5].

Without findall, you can try

filter_list(In, Out) :- filter_list(In, _, Out).

filter_list([], [], []).

filter_list([H|T], L1, L2) :-
             filter_list(T, LL1, LL2),
             (   member(H, LL1)
             ->  L1 = LL1, L2 = LL2
             ;   (select(H, LL2, L2)
                 ->  L1 = [H|LL1]
                 ;   L1 = LL1, L2 = [H|LL2])).