将列表元素的连续重复项打包到Prolog中的子列表中 [英] Pack consecutive duplicates of list elements into sublists in Prolog

问题描述

对于返回

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

Pack consecutive duplicates of list elements into sublists. If a list contains repeated elements they should be placed in separate sublists.

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

Sample query with expected results:

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

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

I managed to pack elements in sublists but I don't know how to return an answer.

这是我的代码:

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

以下是在跟踪模式下运行的查询:

Here's a query run in trace mode:

?- 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 = [] .

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

I imagine there should be additional line at the end of last rule to somehow bind the result to the input but I have no idea how to do it.

推荐答案

以下是您以逻辑上纯的方式进行操作的方法:使用元谓词 dif/3 结合使用 prolog-dif 的修正变体.让我们现在进行一些查询！

Here's how you could do it in a logically pure way: Use the meta-predicate splitlistIfAdj/3 in combination with dif/3, a reified variant of prolog-dif. Let's do some queries right now!

?- Xs = [a], splitlistIfAdj(dif,Xs,Pss).
Xs  = [ a ],
Pss = [[a]].                                    % succeeds deterministically

?- Xs = [a,a,a,a,b,c,c], splitlistIfAdj(dif,Xs,Pss).
Xs  = [ a,a,a,a,  b,  c,c ],
Pss = [[a,a,a,a],[b],[c,c]].                    % succeeds deterministically

?- Xs = [a,a,a,a,b,c,c,a,a,d,e,e,e,e], splitlistIfAdj(dif,Xs,Pss).
Xs  = [ a,a,a,a,  b,  c,c,  a,a,  d,  e,e,e,e ],
Pss = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]].% succeeds deterministically

与不纯代码不同，该实现为单调，可以与非基本术语一起使用:

Unlike impure code, the implementation is monotone and can be used with non-ground terms:

?- Xs = [A,B], splitlistIfAdj(dif,Xs,Pss), A=1, B=2.
Xs = [1,2], A = 1, B = 2, Pss = [[1],[2]].

?- Xs = [A,B], A=1, B=2, splitlistIfAdj(dif,Xs,Pss). % logically equivalent
Xs = [1,2], A = 1, B = 2, Pss = [[1],[2]].

请注意，更多类似以下内容的通用查询也会给出逻辑上合理的答案:

Note that more general queries like the following one also give logically sound answers:

?- Xs = [A,B,C,D], splitlistIfAdj(dif,Xs,Pss).
Xs = [D,D,D,D], Pss = [[D,D,D,D]],           A=B ,     B=C ,     C=D  ;
Xs = [C,C,C,D], Pss = [[C,C,C],[D]],         A=B ,     B=C , dif(C,D) ;
Xs = [B,B,D,D], Pss = [[B,B],[D,D]],         A=B , dif(B,C),     C=D  ;
Xs = [B,B,C,D], Pss = [[B,B],[C],[D]],       A=B , dif(B,C), dif(C,D) ;
Xs = [A,D,D,D], Pss = [[A],[D,D,D]],     dif(A,B),     B=C ,     C=D  ;
Xs = [A,C,C,D], Pss = [[A],[C,C],[D]],   dif(A,B),     B=C , dif(C,D) ;
Xs = [A,B,D,D], Pss = [[A],[B],[D,D]],   dif(A,B), dif(B,C),     C=D  ;
Xs = [A,B,C,D], Pss = [[A],[B],[C],[D]], dif(A,B), dif(B,C), dif(C,D).

这篇关于将列表元素的连续重复项打包到Prolog中的子列表中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！