Deleting unwanted elements from list in PROLOG

Question

I have a list, for example [(1,2), (3,4), (5,2), (4,2), (8,0)], and I want to remove, for example, all elements that are not (_,2). So in this case, I'd end up with a list like this: [(1,2), (5,2), (4,2)]. I was trying:

   conta_pos(NL, _, NL):-
      Idk what to do here, !.

   conta_pos([(L,C)|T], C, _):-
      conta_pos_aux([()], C, _).  

    conta_pos([(_,C)|T], _, _):-
      conta_pos(T, _, _).  

The first argument represents the initial list, the second is the element I want the list to keep, and the third would be my new list.
Keep in mind that I'm very new to Prolog, please.

(The actual thing I want to do is to count the number of elements in the initial that are, in this example (_, 2), so that would 3. I was thinking of then using length\2 to count them, but if you have a better suggestion, I'm all open to it! And if you want to know what the whole thing I have to do is, feel free to ask)

Answer 1

You're describing lists, so you could use DCGs for the task, since they usually yield easily readable code. Furthermore, you could use an additional argument to count the elements in the list as it's being traversed. Consider the following code:

list_filtered_length(L,F,Len) :-    % the filtered list F is described
   phrase(filtered_len(L,Len,0),F). % by the DCG filtered_len//3 

filtered_len([],N,N) -->            % if the list is empty, the counter is the length
   [].                              % and the filtered list is empty
filtered_len([(A,2)|Ps],N,C0) -->   % if the head of the list is (A,2)
   {C1 is C0+1},                    % the counter is increased
   [(A,2)],                         % (A,2) is in the filtered list
   filtered_len(Ps,N,C1).           % the same for the tail
filtered_len([(_,B)|Ps],N,C) -->    % if the head of the list is (_,B)
   {dif(B,2)},                      % with B not being 2, it's not in the list
   filtered_len(Ps,N,C).            % the same for the tail

Querying this predicate with your example yields the desired result:

?- list_filtered_length([(1,2),(3,4),(5,2),(4,2),(8,0)],F,Len).
F = [ (1, 2), (5, 2), (4, 2)],
Len = 3 ;
false.

Obviously, if you want to apply a different filter, you have to rewrite the two recursive DCG rules. It would be nicer to have the filter defined as a separate predicate and to pass it as an argument, therefore making the predicate more versatile. It would also be nice to have the predicate succeed deterministically if there's only a single solution. This can be realized with if_/3 and (=)/3. In order to be used as the first argument of if_/3, the filter predicate needs to reify its truth value as an additional argument:

filter_t((_,X),T) :-
   if_(X=2,T=true,T=false).

As you can see, the last argument is true if the filter condition holds and false otherwise:

?- filter_t((1,1),T).
T = false.

?- filter_t((1,2),T).
T = true.

Now the predicate can be redefined with an additional argument for the filter like so:

list_filtered_by_length(L,LF,F_2,Len) :-    % F_2 is the filter argument
   phrase(filtered_by_len(L,F_2,Len,0),LF).

filtered_by_len([],_F_2,N,N) -->
   [].
filtered_by_len([P|Ps],F_2,N,C0) -->
   {if_(call(F_2,P),(X=[P], C1 is C0+1),
                    (X=[], C1 = C0))},
   X,                                       % X is in the filtered list
   filtered_by_len(Ps,F_2,N,C1).

If the head of the list meets the filter condition (call(F_2,P)), it is in the filtered list (X=[P]) and the counter is increased (C1 is C0+1), otherwise it is not in the list (X=[]) and the counter is not increased (C1 = C0).

Now the example query succeeds deterministically:

?- list_filtered_by_length([(1,2),(3,4),(5,2),(4,2),(8,0)],F,filter_t,Len).
F = [ (1, 2), (5, 2), (4, 2)],
Len = 3.

If you want to filter for something else, just define a different filter predicate. For example, if you want to filter all pairs of equal elements from a list of pairs, you can define...

filter2_t(X-Y,T) :-
   if_(X=Y,T=true,T=false).

... and then query:

?- list_filtered_by_length([a-a,b-c,d-d,e-f],F,filter2_t,Len).
F = [a-a, d-d],
Len = 2.

EDIT

Alternatively, you can express this relation quite compactly by using tfilter/3, as suggested by @false in the comments. Just as with the DCG version you pass a reifying filter predicate as third argument that is then used as the first argument of tfilter/3. Subsequently the length of the filtered list is described by the built-in length/2.

list_filtered_by_length(L,FL,F_2,Len) :-
   tfilter(F_2,L,FL),
   length(FL,Len).

The above queries yield the same answers as with the DCG version.

Answer 2

In general, suppose that you have a predicate some_condition(...other_args..., X) that succeeds if you want to keep X and fails otherwise. A simple recursion to do the filter would be:

filter([], _, []).
filter([X|Xs], Condition, Ys) :-
    (    call(Condition, X)
    ->   Ys = [X|Zs]
    ;    Ys = Zs
    ),
    filter(Xs, Condition, Zs).

You can then call this as:

filter(RawList, some_condition(...other args...), FilteredList).

In this specific case, the condition you want to check is whether the argument matches (_,2). The simplistic condition would be:

second_arg_2((_,2)).  % Succeeds if second argument is a 2

You can make the condition as sophisticated as you wish to handle more cases.

Then you can call:

| ?- filter([(1,2), (3,4), (5,2), (4,2), (8,0)], second_arg_2, R).

R = [(1,2),(5,2),(4,2)]

yes

You can then, of course, count the results if you want using length/2.

Answer 3

For the count of (_,2) you can do

conta_pos(In, (_,V), Out) :-
    aggregate(count, X^member((X,V), In), Out).

Result :

?- conta_pos( [(1,2), (3,4), (5,2), (4,2), (8,0)], (_,2), Out).
Out = 3.

Answer 4

Filtering elements matching (via unification) with a template, we have two recursive rules (one for when the element matches Z, and one for when the element does not match):

filter([X|Xs],Z,[X|Ys]) :- % X is part of the output
    copy_term(Z,E),        % copy free variables (e.g. the _ in (_,2))
    E=X,                   % matches with template Z
    filter(Xs,Z,Ys).       % recurse

filter([X|Xs],Z,Ys) :-     % X is not part of the output
    copy_term(Z,E),        % copy free variables
    E\=X,                  % does NOT match with template Z
    filter(Xs,Z,Ys).       % recurse

filter([],_,[]).           % base step

We have to use copy_term/2 to generate a new copy of free variables, otherwise it will ground the matching variables at the first step and try to match the grounded template against the remaining elements, and would fail.

?- filter([(1, 2), (3, 4), (5, 2), (4, 2), (8, 0)], (_, 2), Y), length(Y, Count).
Y = [(1, 2),  (5, 2),  (4, 2)],
Count = 3

 

Alternatively, you can directly count the matching elements with a recursive predicate, which works exactly the same as the previous solution:

count([X|Xs],Z,Count) :-
    copy_term(Z,E),
    E=X,
    count(Xs,Z,Count1),
    Count is Count1 + 1.

count([X|Xs],Z,Count) :-
    copy_term(Z,E),
    E\=X,
    count(Xs,Z,Count).

count([],_,0).

Test:

?- count([(1,2), (3,4), (5,2), (4,2), (8,0)], (_,2), Count).
Count = 3

 

The two recursive rules can be merged into one, with the conditional (->) operator:

count([X|Xs],Z,Count) :-
    copy_term(Z,E),
    count(Xs,Z,Count1),
    ( E=X -> Count is Count1 + 1 ; Count=Count1 ).

count([],_,0).