Пролог сжимает список с количеством повторных ответов

Question

У меня есть список элементов, который содержит количество друзей, которых имеет человек.

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

Я хочу сжать этот список и получить следующий

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

Я создал пользователяи удалите первое появление.

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).

Я правильно понимаю свои ответы, но Пролог возвращает один и тот же ответ несколько раз.Почему это происходит?

Пример:

?- 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.

Answer 1

Другой способ - использовать агрегат / 3 (который работает с SWI-Prolog):

compress(In, Out) :-
     aggregate(set(friends(P,S)), aggregate(sum(X), member(friends(P,X), In), S), Out).

Результат:

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

Answer 2

Одно небольшое изменение устраняет проблему дубликатов ответов:

....
....
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), 
....
....

Это также дает объяснение: member успешно выполняется более одного раза, если у вас есть дубликаты в списке, но вы намеревались использовать толькопервый результат.

Answer 3

Если вы измените определение delete_first/3 ...

delete_first([X|Y], X, Y).
delete_first([X|Y], E, [X|L]) :- 
   X \= E, 
   delete_first(Y, E, L).

... вам больше не нужно использовать member/2 ...

compress([], []).
compress([friends(P,C)|R], S) :- 
   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]) :- 
   \+ delete_first(R, friends(P,_), _),
   compress(R, S).

... и дубликаты ответов в вашем примере запроса исчезают:

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

---

Однако при использовании без достаточного количества экземпляров compress/2 может дать ложный ответ (ы):

?- compress([friends(mike,4), friends(joe,3), friends(<b>Any</b>,10)], Xs).
Any = mike, Xs = [friends(mike,14),friends(joe,3)] ;
false.                             % what?! how about Any = joe?

Чтобы защититься от этого, мы можем использовать iwhen/2 примерно так:

list_compressed(Es, Xs) :-
   iwhen(ground(Es), compress(Es,Xs)).

Примеры запросов:

?- list_compressed([friends(mike,4), friends(joe,3), friends(Any,10)], Xs).
<b>ERROR: Arguments are not sufficiently instantiated</b>

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

Answer 4

Извините, что на самом деле не ответил на ваш вопрос и вместо этого дал вам альтернативное решение.

То, что вы делаете, слишком круглое, без каких-либо очевидных преимуществ (но, пожалуйста, исправьте меня, если я ошибаюсь).

Идиоматическим подходом будет сортировка без удаления дубликатов с использованием msort/2.Это принесет записи, которые вам нужно объединить рядом друг с другом.Тогда будет легче сделать математику.

Еще проще, если вы также использовали group_pairs_by_key/2:

friends_compressed(L, C) :-
    maplist(friends_pair, L, Pairs),
    msort(Pairs, Sorted),
    group_pairs_by_key(Sorted, Grouped),
    maplist(counts_sum, Grouped, Summed),
    maplist(friends_pair, C, Summed).

friends_pair(friends(Name, Number), Name-Number).

counts_sum(X-Counts, X-Sum) :-
    sum_list(Counts, Sum).

Большая часть этого кода преобразуется из friends(Name, Count) в Name-Count, но этонаходится вне точки.

Единственное отличие в конечном результате состоит в том, что порядок списка по имени, а не по первому появлению в исходном списке:

?- friends_compressed([friends(mike, 4), friends(joe, 3), friends(mike, 1), friends(mike, 2)], R).
R = [friends(joe, 3), friends(mike, 7)].

Вы можете посмотретьопределение group_pairs_by_key/2 и sum_list/2 в исходном коде SWI-Prolog.