将列表元素的连续重复项打包到 Prolog 中的子列表中

我无法返回问题 9 的答案P-99：九十九个 Prolog 问题 http://www.ic.unicamp.br/~meidanis/courses/mc336/2009s2/prolog/problemas/:

将列表元素的连续重复项打包到子列表中。 如果列表包含重复元素，则应将它们放置在单独的子列表中。

具有预期结果的示例查询：

?- pack([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
X = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]].

我设法将元素打包到子列表中，但我不知道如何返回答案。

这是我的代码：

pack(X,Y) :- pack(X,[],Y).
pack([H,H|T],Acc,X) :- pack([H|T],[H|Acc],X).
pack([H,H1|T], Acc, X) :- 
    H\=H1, 
    Acc1=[H|Acc],
    append(X, [Acc1], X1),
    pack([H1|T],[],X1).
pack([H], Acc, X) :- 
    Acc1=[H|Acc],
    append(X, [Acc1], X1).

这是在跟踪模式下运行的查询：

?- trace, pack([a,a,a,a,b,c,c],X).
   Call: (6) pack([a, a, a, a, b, c, c], _G986) ? creep
   Call: (7) pack([a, a, a, a, b, c, c], [], _G986) ? creep
   Call: (8) pack([a, a, a, b, c, c], [a], _G986) ? creep
   Call: (9) pack([a, a, b, c, c], [a, a], _G986) ? creep
   Call: (10) pack([a, b, c, c], [a, a, a], _G986) ? creep
   Call: (11) a\=b ? creep
   Exit: (11) a\=b ? creep
   Call: (11) _G1100=[a, a, a, a] ? creep
   Exit: (11) [a, a, a, a]=[a, a, a, a] ? creep
   Call: (11) lists:append(_G986, [[a, a, a, a]], _G1105) ? creep
   Exit: (11) lists:append([], [[a, a, a, a]], [[a, a, a, a]]) ? creep
   Call: (11) pack([b, c, c], [], [[a, a, a, a]]) ? creep
   Call: (12) b\=c ? creep
   Exit: (12) b\=c ? creep
   Call: (12) _G1109=[b] ? creep
   Exit: (12) [b]=[b] ? creep
   Call: (12) lists:append([[a, a, a, a]], [[b]], _G1114) ? creep
   Exit: (12) lists:append([[a, a, a, a]], [[b]], [[a, a, a, a], [b]]) ? creep
   Call: (12) pack([c, c], [], [[a, a, a, a], [b]]) ? creep
   Call: (13) pack([c], [c], [[a, a, a, a], [b]]) ? creep
   Call: (14) _G1127=[c, c] ? creep
   Exit: (14) [c, c]=[c, c] ? creep
   Call: (14) lists:append([[a, a, a, a], [b]], [[c, c]], _G1132) ? creep
   Exit: (14) lists:append([[a, a, a, a], [b]], [[c, c]], [[a, a, a, a], [b], [c, c]]) ? creep
   Exit: (13) pack([c], [c], [[a, a, a, a], [b]]) ? creep
   Exit: (12) pack([c, c], [], [[a, a, a, a], [b]]) ? creep
   Exit: (11) pack([b, c, c], [], [[a, a, a, a]]) ? creep
   Exit: (10) pack([a, b, c, c], [a, a, a], []) ? creep
   Exit: (9) pack([a, a, b, c, c], [a, a], []) ? creep
   Exit: (8) pack([a, a, a, b, c, c], [a], []) ? creep
   Exit: (7) pack([a, a, a, a, b, c, c], [], []) ? creep
   Exit: (6) pack([a, a, a, a, b, c, c], []) ? creep
X = [] .

我想在最后一条规则的末尾应该有额外的行以某种方式将结果绑定到输入，但我不知道该怎么做。

首先，您有一个关于 X1 的单例变量警告：

pack([H], Acc, X) :- 
    Acc1=[H|Acc],
    append(X, [Acc1], X1).

整个规则简化为：

pack([H], Acc, X) :- append(X, [[H|Acc]], _).

这肯定不是您想要的，但是看看您这里的内容，我不确定您到底想要什么。一方面，我不会解决这个问题append/3。您的解决方案实际上生成了不同值的列表，这告诉我某处出现了相当严重的失火。

?- pack([a, a, a, a, b, c, c], X).
X = [] ;
X = [_G704] ;
X = [_G704, _G710] ;
X = [_G704, _G710, _G716] ;
X = [_G704, _G710, _G716, _G722] a

我希望我能看到问题，因为在跟踪中我看到您正在正确地构建结果。更有洞察力的人可能会修复您的拼写错误。

无论如何，这就是我想出的：

pack([X|Unpacked], Packed) :- pack(Unpacked, [[X]], Packed).

pack([H|T], [[H|Acc]|Rest], Packed) :- pack(T, [[H,H|Acc]|Rest], Packed).
pack([X|T], [[Y|Acc]|Rest], Packed) :-
    X \= Y,
    pack(T, [[X],[Y|Acc]|Rest], Packed).
pack([], RPacked, Packed) :- reverse(RPacked, Packed).

事实上，差异列表解决方案将允许在不使用append/3或使用reverse/2最后，但我后兜里没有。