Filter list in prolog

5
votes

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 ?

4
prolog

4 Answers

7
votes

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 .

3
votes

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])).
3
votes

without counting...

filter_uniques([],[]).
filter_uniques([H|T],F) :-
    delete(T,H,D),
    ( D=T -> F=[H|R],S=T ; F=R,S=D ),
    filter_uniques(S,R).

a more direct rewrite of your code, with library(yall) support for inlining of the filter predicate (the first argument to include/3)

filt_uniq(L,F) :-
    include({L}/[E]>>aggregate(count,member(E,L),1),L,F).
2
votes

A simple version:

(see the comment by @false below, the version with findall/3 has some inconsistency problems in more complex queries but second version looks ok however it is definitely not so efficient ).

filter_list(L,OutList):-findall(X, (member(X,L),count(X,L,N),N=:=1) , OutList).

count(_,[],0).
count(X,[X|T],N):-count(X,T,N1),N is N1+1.
count(X,[X1|T],N):-dif(X,X1),count(X,T,N).

The predicate filter_list/2 uses findall/3 and simply states find all X that belong to the list L and count returns 1 and store them in OutList.

Example:

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

You could write filter_list/2 without using findall/3 like:

filter_list(L,OutList):- filter_list(L,OutList,L).
filter_list([],[],_).
filter_list([H|T],[H|T1],L):-count(H,L,N), N=:=1, filter_list(T,T1,L).
filter_list([H|T],T1,L):-count(H,L,N), N > 1, filter_list(T,T1,L).