Пролог сжимает список с количеством -- повторяющиеся ответы
У меня есть список элементов, который содержит количество друзей человека.
[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.
Обещание: как можно скорее назначит вознаграждение за чистую версию, которая не требует ошибок инстанцирования для защиты от некорректных случаев.
Ответы 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.
Одно небольшое изменение устраняет проблему дублирующихся ответов:
....
....
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 завершается успешно более одного раза, если у вас есть дубликаты в списке, но вы намеревались использовать только первый результат.
Я подозреваю, что member или memberchk, за которым следует delete_first, — это то же самое, что и select, за которым следует разрез.
есть еще selectchk/3, я думаю. обязательно сделаю что-то подобное. :) Интересно, что двойное отрицание также работает (по крайней мере, для данного запроса... Я имею в виду, что он оставляет X неопределенным...).
Да, действительно есть :)
Двойное отрицание также является более чистой альтернативой циклам, управляемым ошибками. Забавно, двойное отрицание.
Я думаю, вы имели в виду \+ (member(X, [1,2,3]), writeln(X), false). вместо (member(X, [1,2,3]), writeln(X), false ; true)..
Почти. я имел ввиду \+ ( Generator, \+ Goal ) так например \+ ( member(X, [1,2,3]), \+ writeln(X) )
Если изменить определение 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(Any,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).
ERROR: Arguments are not sufficiently instantiated
?- 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.
Другой способ — использовать агрегат/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)].
+1: библиотека (совокупность) так часто не представлена ... должно быть предпочтительным оружием, учитывая, что люди достаточно уверены в агрегировании операторов SQL.
@WillNess добавил запрос и результаты.