Prolog压缩列表并显示重复项数量

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

我可以帮您进行翻译。Prolog返回相同的答案多次，但我的答案是正确的。这是为什么呢？

例如：

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

- AwesomeGuy

---

@WillNess 添加了查询和结果。 - AwesomeGuy

承诺：将尽快为一个纯净版本设置赏金，该版本不需要实例化错误来防止不正确的情况。 - false

Answer 1

另一种方法是使用 aggregate/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)].

- joel76

---

+1：library（aggregate）经常被忽视...但是鉴于人们对聚合SQL运算符有足够的信心，它应该是首选。 - CapelliC

Answer 2

很抱歉没有真正回答你的问题，而是提供了一种替代方案。

你所做的方法非常绕，而且并没有明显的好处（如果我说错了，请纠正我）。

一个惯用的方法是使用 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)].

您可以在SWI-Prolog的源代码中查找group_pairs_by_key/2和sum_list/2的定义。

- User9213

Answer 3

一个小的修改可以解决重复答案的问题：

....
....
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 函数会成功多次，但你只打算使用第一个结果。

- Will Ness

---

我怀疑在 member 或 memberchk 后面跟着 delete_first 和在 select 后面跟着一个剪切是一样的。 - User9213

还有selectchk/3，我认为它可以做类似的事情。有趣的是，双重否定也起作用（至少对于给定的查询...我的意思是，它使X未实例化...）。 - Will Ness

是的，确实有 :) - User9213

双重否定也是相对于以失败为驱动的循环而言更加简洁的选择。有趣的是，双重否定。 - User9213

我猜你的意思是 \+ (member(X, [1,2,3]), writeln(X), false). 而不是 (member(X, [1,2,3]), writeln(X), false ; true).。 - Will Ness

几乎了解。我指的是 \+ ( Generator, \+ Goal )，例如 \+ ( member(X, [1,2,3]), \+ writeln(X) )。 - User9213

Answer 4

如果您更改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(任何人,10)], Xs).
任何人 = mike, Xs = [friends(mike,14),friends(joe,3)] ;
false.                             % 什么？！那 joe 怎么办？

为了防止这种情况，我们可以使用iwhen/2，像这样：

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

示例查询:

？- list_compressed([friends(mike,4), friends(joe,3), friends(任何,10)], Xs).
错误：参数未充分实例化

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

- repeat