Build a new list of elements which appears more than 3 times in old list in Prolog

user_12903822 0
Viewed 74

My main task - build a new list of elements (numbers) that appear in the old list more than three times.

Asking query: res([1,2,2,3,3,3,4,4,4,4,5,5,5,5,5],X). Expected result: X = [4, 5]

I have a code that counts the number of occurrences of each number:

count(_, [], 0).
count(Num, [H|T], X) :- dif(Num,H), count(Num, T, X).
count(Num, [H|T], X) :- Num = H, count(Num, T, X1), X is X1 + 1.
res(A, X) :- findall(X,count(_,A,X),X).

But it works little bit wrong - it gives X = [0, 5, 4, 3, 2, 1] instead X = [1, 2, 3, 4, 5].

I ignored this problem for while and tried this to finish main task:

count(_, [], 0).
count(Num, [H|T], X) :- dif(Num,H), count(Num, T, X).
count(Num, [H|T], X) :- Num = H, count(Num, T, X1), X is X1 + 1, X<3, X is Num.
res(A, X) :- findall(X,count(_,A,X),X).

But gives strange result: X = [0, 1]

Where i'm wrong? Thank you.

prolog
2 Answers

Reusing your first count predicate,

%countElement(Element, List, Nb_Element_in_List)
countElement(_, [], 0).
countElement(Num, [H|T], X) :- dif(Num,H), countElement(Num, T, X).
countElement(Num, [H|T], X) :- Num = H, countElement(Num, T, X1), X is X1 + 1.

Here is the predicate query/1

query(X) :- 
    L = [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5],
    countOneByOne(L, L, [], X).

%countOneByOne(A1,A2,In,Out)
%For each Element of A1, if it satisfies countElement(Element,A2,N) & N>4, is accumulated with In, to give Out
%Out is the list of Elements of A1 that satisfies countElement(Element,A2,N) & N>4, added to In

countOneByOne([], _, X, X).
countOneByOne([H|Xs], L, X1, X2) :-
    countElement(H, L, N), N<4, !,
    countOneByOne(Xs, L, X1, X2).
countOneByOne([H|Xs], L, X1, X2) :- 
    removeElement(Xs, H, Ss),
    countOneByOne(Ss, L, [H|X1], X2).

%remove(List, Element, List_Without_Element)    
removeElement(    [], _, []).
removeElement([X|Xs], H, [X|R1]) :-
    dif(X,H), removeElement(Xs, H, R1).
removeElement([X|Xs], X, R1) :-
    removeElement(Xs, X, R1).
user_13104170

Not an answer but another approach using foldl/4 and the dict of SWI-Prolog.

Whenever I hear "scan through a list to perform a computation with a final result at the end", the appropriate approach is probably the "accumulator idiom". One hands a data structure (the "accumulator") between the calls where something happens with a list element, "accumulating" the result. foldl/N is meant to provide boilerplate code around this.

In this case the accumulator is the SWI_prolog dict accumulating "occurrence counts", which happens at each call to inc_for_key/3. At the end, we just need to select the entries with a high enough occurence count:

filter_occurrences(List,Limit,Reacheds,Finals) :-
   foldl(inc_for_key,List,_{},Finals),
   findall(Key,(Finals.Key >= Limit),Reacheds).

inc_for_key(Key,DictIn,DictOut) :-
   (get_dict(Key,DictIn,X) -> succ(X,XP) ; XP=1),
   put_dict(Key,DictIn,XP,DictOut).

Testing using plunit

:- begin_tests(filter_occurrences_less_than_n).

test("filter empty list",true(R == [])) :-
   filter_occurrences([],3,R,_).

test("filter nonempty list #1 (limit 3)",true([R,Finals] == [[a,c],foo{a:4,b:2,c:3,d:1,e:1,f:1}])) :-
   filter_occurrences([a,b,c,d,c,e,b,a,a,f,a,c],3,R,Finals),
   dict_pairs(Finals,foo,_). % Sets the tag of the Finals dict to "foo"

test("filter nonempty list #2 (limit 4)",true([R,Finals] == [[a],foo{a:4,b:2,c:3,d:1,e:1,f:1}])) :-
   filter_occurrences([a,b,c,d,c,e,b,a,a,f,a,c],4,R,Finals),
   dict_pairs(Finals,foo,_). % Sets the tag of the Finals dict to "foo"

test("filter nonempty list #3 (limit 5)",true([R,Finals] == [[],foo{a:4,b:2,c:3,d:1,e:1,f:1}])) :-
   filter_occurrences([a,b,c,d,c,e,b,a,a,f,a,c],5,R,Finals),
   dict_pairs(Finals,foo,_). % Sets the tag of the Finals dict to "foo"

:- end_tests(filter_occurrences_less_than_n).

And so:

?- run_tests.
% PL-Unit: filter_occurrences_less_than_n .... done
% All 4 tests passed
true.
user_8844630
Related