Prolog compress list with quantity — repeated answers

  • A+
Category:Languages

I have a list of elements which contains the number of friends a person has.

[friends(mike, 4), friends(joe, 3), friends(mike, 1), friends(mike, 2)] 

I want to compress this list and obtain the following

[friends(mike, 7), friend(joe, 3)] 

I created member, and delete first appearance.

member(E, [E|_]). member(E, [_|Y]) :-      member(E, Y).  delete_first([], _, []). delete_first([X|Y], X, Y). delete_first([X|Y], E, [X|L]) :-      X /= E,      delete_first(Y, E, L).  compress([], []). compress([friends(P, C)|R], S) :-      member(friends(P, X), R),      delete_first(R, friends(P, X), E),      N is C + X,      compress([friends(P, N)|E], S). compress([friends(P, C)|R], [friends(P, C)|S]) :-      not(member(friends(P, _), R)),      compress(R, S). 

I'm getting my answers right but Prolog returns the same answer several times. Why is that happening?

Example:

?- compress([friends(mike, 4), friends(joe, 3), friends(mike, 1),               friends(mike, 2), friends(joe,4), friends(mike, 3)],X). X = [friends(mike, 10), friends(joe, 7)] ; X = [friends(mike, 10), friends(joe, 7)] ; X = [friends(mike, 10), friends(joe, 7)] ; X = [friends(mike, 10), friends(joe, 7)] ; X = [friends(mike, 10), friends(joe, 7)] ; X = [friends(mike, 10), friends(joe, 7)] ; false. 

 


One small alteration fixes the problem of duplicate answers:

.... .... compress([], []). compress([friends(P, C)|R], S) :-      % member(friends(P, X), R), !,          NB   either add a cut here     % /+( /+( member(friends(P, X), R))),   NB   or use double negation     memberchk(friends(P, X), R),            NB   or use `memberchk/2` if available     delete_first(R, friends(P, X), E),  .... .... 

This also provides the explanation: member succeeds more than once if you have duplicates in the list, but you only intended to use the first result.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: