Prolog程序创建一个包含第一个重复元素的列表

Question

我需要实现这个功能：

cod_first(X, L, Lrem, Lfront).

Lfront 包含 X 的所有副本，这些副本位于 L 的开头，包括 X； Lrem 是其余元素的列表。

我试过使用 append 来实现它，但我对 Prolog 很陌生，有点迷路了。

程序的预期输出是这样的：

?- cod_first(1, [1, 1, 2, 3], Lrem, Lfront) 
Lrem = [2, 3],
Lfront = [1, 1, 1];
false.

?- cod_first(1, [2, 3, 4], Lrem, Lfront)
Lrem = [2, 3, 4],
Lfront = [1];
false.

更新：我发现这个函数将相同的元素打包到列表中：

pack([], []).
pack([X], [[X]]).
pack([X, X| L], [[X| Xs]| R]) :-
    pack([X| L], [Xs| R]).
pack([X, Y| L], [[X]| R]) :-
    X \= Y,
    pack([Y| L], R).

我认为这个功能可以适应我正在寻找的那个，有帮助吗？

Answer 1

首先让我们检查一下您找到的代码！我将通过考虑 all 个列表来测试它，从最短的一个开始：

?- N=N, length(Xs,N), pack(Xs, Xss).
   N = 0, Xs = [], Xss = []
;  N = 1, Xs = [_A], Xss = [[_A]]
;  N = 2, Xs = [_A,_A], Xss = [[_A,_A]]
;  N = 3, Xs = [_A,_A,_A], Xss = [[_A,_A,_A]]
;  N = 4, Xs = [_A,_A,_A,_A], Xss = [[_A,_A,_A,_A]]
;  ...

因此，根据此查询，您的代码仅适用于所有元素都相同的列表。事实上，目标 X \= Y 对此负责。用 dif(X, Y) 更好地表达不等式。通过这个小改动，我们得到：

 ?- N=N, length(Xs,N), pack(Xs, Xss).
    N = 0, Xs = [], Xss = []
 ;  N = 1, Xs = [_A], Xss = [[_A]]
 ;  N = 2, Xs = [_A,_A], Xss = [[_A,_A]]
 ;  N = 2, Xs = [_A,_B], Xss = [[_A],[_B]], dif(_A,_B)
 ;  N = 3, Xs = [_A,_A,_A], Xss = [[_A,_A,_A]]
 ;  N = 3, Xs = [_A,_A,_B], Xss = [[_A,_A],[_B]], dif(_A,_B)
 ;  N = 3, Xs = [_A,_B,_B], Xss = [[_A],[_B,_B]],  dif(_A,_B)
 ;  N = 3, Xs = [_A,_B,_C], Xss = [[_A],[_B],[_C]], dif(_A,_B), dif(_B,_C)
 ;  N = 4, Xs = [_A,_A,_A,_A], Xss = [[_A,_A,_A,_A]]
 ;  ...

现在我们真的得到了所有的解决方案。让我们考虑 N = 2 的两个答案。第一个说 Xs 的元素都相等，Xss 只包含一个元素。第二个说当Xs的元素不同时，它们显示在Xss的单独元素中。请注意 dif(_A,_B)，它确保只选择不同的术语。

但是，您只对一个这样的拆分感兴趣：

cod_first(X, [], [], [X]).
cod_first(X, [X|Es], Lrem, [X|Xs]) :-
   cod_first(X, Es, Lrem, Xs).
cod_first(X, [E|Es], [E|Es], [X]) :-
   dif(X,E).

?- N=N, length(Xs, N), cod_first(X, Xs, Lrem, Lfront).
   N = 0, Xs = [], Lrem = [], Lfront = [X]
;  N = 1, Xs = [X], Lrem = [], Lfront = [X,X]
;  N = 1, Xs = [_A], Lrem = [_A], Lfront = [X], dif(_A,X)
;  N = 2, Xs = [X,X], Lrem = [], Lfront = [X,X,X]
;  N = 2, Xs = [X,_A], Lrem = [_A], Lfront = [X,X], dif(_A,X)
;  N = 2, Xs = [_A,_B], Lrem = [_A,_B], Lfront = [X], dif(_A,X)
;  N = 3, Xs = [X,X,X], Lrem = [], Lfront = [X,X,X,X]
;  N = 3, Xs = [X,X,_A], Lrem = [_A], Lfront = [X,X,X], dif(_A,X)
;  N = 3, Xs = [X,_A,_B], Lrem = [_A,_B], Lfront = [X,X], dif(_A,X)
;  N = 3, Xs = [_A,_B,_C], Lrem = [_A,_B,_C], Lfront = [X], dif(_A,X)
;  N = 4, Xs = [X,X,X,X], Lrem = [], Lfront = [X,X,X,X,X]
;  ...

这是我更喜欢使用 library(reif) 的另一个版本为了 SICStus 和 SWI.

cod_first2(X, Es, Lrem, [X|Xs]) :-
   cod_first2i(Es, X, Xs, Lrem).

cod_first2i([], _, [], []).
cod_first2i([E|Es], X, Xs0, Ys) :-
   if_( E = X
      , ( Xs0 = [X|Xs], cod_first2i(Es, X, Xs, Ys) )
      , ( Xs0 = [], Ys = [E|Es] )
      ).

这样效率更高，但给出的答案完全相同。

Prolog程序创建一个包含第一个重复元素的列表

Prolog program to create a list with first duplicate elements

prolog

run-length-encoding