消除连续重复

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

我们从谓词的名称开始。

为什么要用命令式[=53=]来表示关系？一个好的 Prolog 程序可以在 所有方向 中使用，而命令式总是暗示特定的方向或使用模式。因此，选择一个 声明性名称 并以通用性和 logical-purity.

为目标
接下来，最一般的查询呢：

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

从这里拿走！改进确定性，找到一个更好的名字等

Answer 2

在(+1) 的基础上，为什么不提高确定性 像这样的案例：

?- phrase(compression([a,a,b,b,b,c,c,c,c,d]), Xs).
Xs = [a, b, c, d] ;
false.

对于 ; false，SWI prolog-toplevel 表明目标没有确定地成功。

我们可以通过使用 if_//3—the dcg analogue of if_/3:

来改进 compression_//2

compression_([], _) --> [].
compression_([X|Xs], L) -->
   if_(X = L,                           % is this item equal to previous one?
       compression_(Xs, L),             %   yes: old "run" goes on
       ([X], compression_(Xs, X))).     %    no: new "run" starts

示例查询：

?- phrase(compression([a,a,b,b,b,c,c,c,c,d]), Xs).
Xs = [a, b, c, d].                            % succeeds deterministically

消除连续重复

Eliminate consecutive duplicates

list

prolog

prolog-dif

logical-purity