如何用 Prolog 中的前一个元素非递归地替换列表的 "rep" 元素

Question

我正在尝试以非递归方式复制“rep”元素之前的列表元素。例如，我有列表

[1,2,rep,3,4,5]

我想以

结束

[1,2,2,3,4,5]

或

[rep,1,2,3,4,5]

想要

[1,2,3,4,5]

到目前为止我有：

element_repeat_non(List,Sol):-
  findall(X,element_inner(List,X),Sol).
        
element_inner(List,X):-
  member(X,List),
  not(X==rep).

然而，这只会忽略 rep 元素和 returns 没有它的列表，在

的情况下给出所需的结果

[rep,1,2,3,4,5]

但在

的情况下则不然

[1,2,rep,3,4,5]

我不知道如何保留前一个元素以便替换“rep”元素。如果可能的话，我想避免使用条件检查(if_then_else).

欢迎任何建议。提前致谢！

Answer 1

考虑到输入列表中的原子 rep 最多 一次出现 （正如您在上一条评论中所述），一个可能的解决方案如下：

% repeat_previous(+List, -NewList)

  repeat_previous([rep|L], L).
  repeat_previous(L, L) :-
      not(append(_, [rep|_], L)).
  repeat_previous(L, S) :-
      append(Xs, [Y,rep|Ys], L),
      append(Xs, [Y,Y|Ys], S).

示例：

?- repeat_previous([1,2,3,4,5], L).
L = [1, 2, 3, 4, 5] ;
false.

?- repeat_previous([rep,1,2,3,4,5], L).
L = [1, 2, 3, 4, 5] ;
false.

?- repeat_previous([1,2,rep,3,4,5], L).
L = [1, 2, 2, 3, 4, 5] ;
false.

?- repeat_previous([1,2,3,4,5,rep], L).
L = [1, 2, 3, 4, 5, 5] ;
false.

Answer 2

稍微改变规则，使用DCG：

elem_repeat_dcg(Lst, LstRepeated) :-
    phrase(elem_repeated, Lst, LstRepeated).

% If starts with rep, then just use the remainder
elem_repeated --> [rep], !.
elem_repeated --> elem_repeating.

% Perform the repeat
elem_repeating, [Prev, Prev] --> [Prev], [rep], !.
% Loop through list
elem_repeating, [NotRep] --> [NotRep], !, elem_repeating.
% Accept end of list, if rep is not found
elem_repeating --> [].

结果 swi-prolog：

?- elem_repeat_dcg([1,2,rep,3,4,5], LstRepeated).
LstRepeated = [1,2,2,3,4,5].

?- elem_repeat_dcg([rep,3,4,5], LstRepeated).
LstRepeated = [3,4,5].

?- elem_repeat_dcg([1,2,3,4,5], LstRepeated).
LstRepeated = [1,2,3,4,5].

?- time(elem_repeat_dcg([1,2,rep,3,4,5,6,7,8,9], LstRepeated)).
% 4 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 104430 Lips)
LstRepeated = [1,2,2,3,4,5,6,7,8,9].

这里是 DCG 部分的变体，结果相同：

% If starts with rep, then just use the remainder
elem_repeated --> [rep], !.
elem_repeated, [First] --> [First], elem_repeating(First).

% Perform the repeat
elem_repeating(E), [E] --> [rep], !.
% Loop through list
elem_repeating(_), [E] --> [E], !, elem_repeating(E).
% Accept end of list, if rep is not found
elem_repeating(_) --> [].

出题者可能想要这样的问题：

% This is what NOT to do
elem_repeat(Lst, LstRepeated) :-
    append([Before, [rep], After], Lst),
    append([_, [RepElem]], Before),
    append([Before, [RepElem], After], LstRepeated).

... 这 破坏性能 不只是使用列表的尾部，在执行替换之后 - 这是差异列表可以做什么...并且 DCG 在幕后使用差异列表。

Answer 3

不能用递归，不能用分支，那用scanl/4怎么样？

rep(rep, Prev, Prev).
rep(  E,    _,    E) :- dif(E, rep).

reps_plain(In, Out) :-
    scanl(rep, In, nil, [nil,X|Xs]),
    ( (X = nil,     Out = Xs)
    ; (dif(X, nil), Out = [X|Xs])).

scanl 用于执行运行求和之类的操作，即它获取当前值和先前值的输出，并用它们调用目标。使用它来携带具有先前值的状态以重复。但是，对于第一个值 scanl 没有以前的值可以使用，所以你需要提供一个（这里我使用了 nil），所以列表总是出现 [nil|_] 如果你把 [rep,1,2,3] 然后列表出来 [nil,nil|_] 重复前一个值，即初始占位符值；那是因为这并不是真正构建 scanl 的目的。每个 scanl 步骤都必须输出一个值，它不能从列表中删除一个条目。所以最后它删除了两个或一个 nil.

Answer 4

这是一个non-recursive解决方案：

element_repeat( []         ,      []  ) .
element_repeat( [rep|Xs]   ,      Xs  ) .
element_repeat( [X,rep|Xs] , [X,X|Ys] ) .
element_repeat( [X,Y|Xs]   , [X,Y|Ys] ) :- Y \= rep, element_repeat(Xs,Ys) .

因为TRO（尾递归优化）将其转化为迭代

如果要使用 append/3，我会这样处理：

element_repeat( [rep|Xs] , Xs ) :- ! .
element_repeat( Xs       , Ys ) :-
    append( Pfx, [X,rep|Sfx] , Xs ) ,
    append( Pfx,   [X,X|Sfx] , Ys ) .

Answer 5

我再试一次：这里没有递归； length 作为生成器没有什么可以递归的；只是失败驱动的循环、回溯、数据库更新和最终统一：

:- dynamic(rep/2).

rep([], []).

derep(In, Out) :-
    length(_, _),
    rep(TempA,TempB),
    assertz((rep([A|TempA], [A|TempB]):-dif(A,rep))),
    assertz((rep([A,rep|TempA], [A,A|TempB]))),
    rep(In, Out),
    retractall(rep(_,_)),
    assertz(rep([], [])).

?- derep([2,3,rep,4,5], X).
X = [2, 3, 3, 4, 5] ;

如何用 Prolog 中的前一个元素非递归地替换列表的 "rep" 元素

How to non-recursively replace "rep" element of a list with the previous element in Prolog

prolog