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

Question

I am trying to duplicate the element of a list before the "rep" element, in a NON-recursive way. For example, I have the list

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

and I want to end up with

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

or

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

and want

[1,2,3,4,5]

So far I have:

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

This, however, only ignores the rep element and returns a list without it, giving the desired result in the case of

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

but not in the case of

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

I can't figure out how I can keep the previous element so I can replace the "rep" element. If possible, I would like to avoid using a condition check(if_then_else).

Any recommendations are welcome. Thanks in advance!

Answer 1

Considering that there can be at most one occurrence of the atom rep in the input list (as you have stated in your last comment), a possible solution is as follows:

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

Examples:

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

Slightly bending the rules, to use 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 --> [].

Result in 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].

And here is a variation of the DCG portion, with the same results:

% 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(_) --> [].

Whoever set the question is probably wanting the likes of:

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

... which ruins performance by not just using the tail of the list, after the replacement has been performed - which is what difference lists can do... and DCGs use difference lists behind the scenes.

Answer 3

Can't use recursion, can't use branching, then how about using 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 is built to do things like running sums, i.e. it takes the current value and the output of the previous value and calls the goal with those. Using this to carry the state with the previous value to repeat. However, for the first value scanl has no previous value to use so you need to provide one (here I've used nil), so the list always comes out [nil|_] and if you put [rep,1,2,3] then the list comes out [nil,nil|_] repeating the previous value which is the initial placeholder value; that's because this is not really what scanl is built for. Each scanl step has to output a value it can't drop an entry from the list instead. So at the end it removes either two or one nil.

Answer 4

This is a non-recursive solution:

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

because TRO (tail recursion optimization) converts it into iteration.

If one were to use append/3, I would approach it like so:

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

Answer 5

I'll try again: no recursion here; length as a generator has nothing to recurse over; just failure driven loop, backtracking, database updates, and eventually unification:

:- 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] ;