Prolog. Remove from the first list items that have an even number of occurrences in the second list

user_19144783 0
Viewed 29

I'm just starting to learn how to work with lists in prolog and I tried to make a program on the example of similar tasks, but it does not work. The task is - Remove from the first list items that have an even number of occurrences in the second list.

I have such logic in this functions:

  1. Function counter should return a Quantity of some element at the list.
  2. Function remove ignore of elements which has even quantity at the second list.

My code:

counter(_,[],0).

counter(Number, [H|T], Quantity):- 
    Number =:= H,
    UpdatedQuantity is Quantity + 1,
    counter(Number, T, UpdatedQuantity).
    
counter(Number, [H|T], Quantity):- 
    Number =\= H,
    counter(Number, T, Quantity).


remove([], [], []).

remove([H1|T1], T2, [H1 | T1]) :-
    counter(H1, T2, Quantity),
    Quantity mod 2 =:= 0,
    remove(T1, T2, T1).
    
remove([H1|T1], T2, T1) :-
    counter(H1, T2, Quantity),
    Quantity mod 2 =\= 0,
    remove(T1, T2, T1).

For example, remove([1,2,3,4][1,1,2,3,3,3,4,4,4,4,5,6,7,7], Res) will return Res = [2,3,4,5,7,7]

prolog
1 Answers

Modify the second clause of predicate counter/3 as follows:

  • First find the solution to a simpler instance of the problem.
  • Then use that solution to get the solution to the original instance of the problem.
counter(_, [], 0).

counter(Number, [H|T], UpdatedQuantity):-
    Number =:= H,
    counter(Number, T, Quantity),    
    UpdatedQuantity is Quantity + 1. 

counter(Number, [H|T], Quantity):-
    Number =\= H,
    counter(Number, T, Quantity).

Modify predicate remove/3 as follows:

  • Replace first clause with remove([], _, []), since the second list doesn't need to be empty to stop the recursion.
  • In the last two clauses, replace T1 with T3 (a fresh variable) when it appears in the third argument, since the resulting list may not be equal to the first input list.
  • Also, swap the conditions used in the last two clauses; otherwise, you will remove items that have an odd number of occurrenes.
remove([], _, []).

remove([H1|T1], T2, [H1|T3]) :-
    counter(H1, T2, Quantity),
    Quantity mod 2 =\= 0,
    remove(T1, T2, T3).

remove([H1|T1], T2, T3) :-
    counter(H1, T2, Quantity),
    Quantity mod 2 =:= 0,
    remove(T1, T2, T3).

Example:

?- remove([1,2,3,4,5],[1,1,2,2,2,4], Res).
Res = [2, 4] ;
false.

Improved solution Avoid spurious choice points and redundant call of counter/3.

improved_counter([], _, 0).
improved_counter([H|T], Number, UpdatedQuantity):-
    improved_counter(T, Number, Quantity),
    (   Number =:= H
    ->  UpdatedQuantity is Quantity + 1
    ;   UpdatedQuantity is Quantity ).

improved_remove([], _, []).
improved_remove([H1|T1], T2, Res) :-
    improved_counter(T2, H1, Quantity), % solve this goal only once!
    (   Quantity mod 2 =:= 0
    ->  Res = T3
    ;   Res = [H1|T3] ),
    improved_remove(T1, T2, T3).

Example:

?- improved_remove([1,2,3,4,5],[1,1,2,2,2,4], Res).
Res = [2, 4].
user_115359400
Related