消除连续重复

Question

消除列表元素的连续重复.

我的解决方案是:

compress([X,X|Xs], Q) :-
   compress([X|Xs], Q).
compress([X,Y|Xs], Q) :-
   X \= Y,
   compress([Y|Xs], QR),
   append([X], QR, Q).
compress([X|[]], Q) :-
   compress([], QR),
   append([X], QR, Q).
compress([], []).

并且,由于我是初学者并且我没有逻辑范例的经验,我请求您说出我可以改进的内容以及为什么我的解决方案不尽如人意.

例如,X \= Y对我来说并不漂亮.

Answer 1

我们从谓词的名称开始.

为什么使用命令来表示关系？一个好的Prolog程序可用于所有方向,而命令总是建议一个特定的方向或使用模式.因此,选择声明性名称并以通用性和逻辑纯度为目标.

接下来,最常见的查询:

?- compress(Ls, Cs).
ERROR: Out of local stack

不是很好!我们希望这会产生至少几个答案.

如果我们使用迭代深化怎么办:

?- length(Ls, _), compress(Ls, Cs).
Ls = Cs, Cs = [] ;
Ls = Cs, Cs = [_G841] ;
Ls = [_G841, _G841],
Cs = [_G841] ;
Ls = [_G841, _G841, _G841],
Cs = [_G841] .

哼!缺少相当多的答案!元素不同的情况怎么样？正如您已经直观地预期的那样,使用不纯的谓词会导致这种影响.

因此,使用prolog-dif,即dif/2表示两个术语不同.它可以在各个方向使用!

此外,DCG(dcg)在描述列表时通常很有用.

那么,总的来说,这是怎么回事:

compression([])     --> [].
compression([L|Ls]) --> [L], compression_(Ls, L).

compression_([], _) --> [].
compression_([X|Xs], L) -->
        (   { X = L },
            compression_(Xs, L)
        ;   { dif(X, L) },
            [X],
            compression_(Xs, X)
        ).

我们使用接口谓词phrase/2来处理DCG.

用法示例:

?- phrase(compression(Ls), Cs).
Ls = Cs, Cs = [] ;
Ls = Cs, Cs = [_G815] ;
Ls = [_G815, _G815],
Cs = [_G815] .

?- length(Ls, _), phrase(compression(Ls), Cs).
Ls = Cs, Cs = [] ;
Ls = Cs, Cs = [_G865] ;
Ls = [_G865, _G865],
Cs = [_G865] ;
Ls = Cs, Cs = [_G1111, _G1114],
dif(_G1114, _G1111) .

从这里拿走吧!改善决定论,找到更好的名字等.