Prolog insert element after first occurrence

Question

How I can add an element E right after the first occurrence of X in list Xs?

Example:

?- insert_right_behind(5,10,[2,4,10,12],Xs).
Xs = [2,4,10,5,12].                     % expected answer

At this moment, I have problems understanding the recursion that needs to be made since I am new to the language.

Thanks in advance!

Insertion takes place one time, only after the first element is encountered. — Dizeme, Sep 30 '13 at 18:52

score 2 · Answer 1 · edited May 23 '17 at 11:44

In the previous answer most successful queries left behind useless choicepoints.

We can avoid these choicepoints by using if_/3 and (=)/3 like so:

item_following_in_inserted(I,J,[X|Xs],Ys0) :-
   if_(J = X,
       Ys0 = [J,I|Xs],
       (Ys0 = [X|Ys], item_following_in_inserted(I,J,Xs,Ys))).

Let's run some queries!

?- item_following_in_inserted(5,10,[2,4,12],Xs).
false.                                               % OK, unchanged

?- item_following_in_inserted(5,10,[2,4,10,12],Xs).
Xs = [2,4,10,5,12].                                  % succeeds deterministically

?- item_following_in_inserted(5,10,[2,4,10,12,10],Xs).
Xs = [2,4,10,5,12,10].                               % succeeds deterministically

?- item_following_in_inserted(I,E,Xs,Ys).
  Xs = [      E|_Z], Ys = [      E,I|_Z]             % OK, unchanged
; Xs = [   _A,E|_Z], Ys = [   _A,E,I|_Z], dif(E,_A)
; Xs = [_A,_B,E|_Z], Ys = [_A,_B,E,I|_Z], dif(E,_A), dif(E,_B)
...

lurker · Accepted Answer · 2013-10-01T02:58:31.010

Use three predicate clauses:

% Inserting after in an empty list is an empty list:
insert_after( _X, _Y, [], [] ).

% If the "after" item is at the head of the list, then the "insert" item can go after it:
insert_after( X, Y, [Y|T], [Y,X|T] ).

% If the head of the list isn't the "after" item, then the result will be
% this with a new tail list that has the "insert" item inserted:
insert_after( X, Y, [H|T], [H|L] ) :-
    Y \= H,
    insert_after( X, Y, T, L ).

If the "after" item doesn't exist in the given list, then insert_after/4 will yield the original list. By removing the first insert_after clause above, it will just fail for that case.

Thank you, this solution works as intended and it's also nice that you have provided some comments to your answer. — Dizeme, Sep 30 '13 at 18:59

score 1 · Answer 3 · edited May 23 '17 at 12:23

Let's keep it simple and use append/3, meta-predicate maplist/2 and prolog-dif like so:

item_following_in_inserted(I,J,Xs,Ys) :-
   append(Prefix,[J  |Suffix],Xs),
   maplist(dif(J),Prefix),
   append(Prefix,[J,I|Suffix],Ys).

Done! It's query time... First, let's run the query the OP gave:

?- item_following_in_inserted(5,10,[2,4,10,12],Xs).
  Xs = [2,4,10,5,12]               % succeeds, but leaves behind choicepoint
; false.

What if the item is not a member of the given list?

?- item_following_in_inserted(5,10,[2,4,   12],Xs).
false.                             % fails, as expected: 10 is absent

Let's check that we only insert after the first occurrence—and nowhere else!

?- item_following_in_inserted(5,10,[2,4,10,12,10],Xs).
  Xs = [2,4,10,5,12,10]            % single solution
; false.                           % terminates universally

What about the most general query of item_following_in_inserted/4?

?- item_following_in_inserted(I,E,Xs,Ys).
  Xs = [         E|_Z], Ys = [         E,I|_Z]
; Xs = [      _A,E|_Z], Ys = [      _A,E,I|_Z], dif(E,_A)
; Xs = [   _A,_B,E|_Z], Ys = [   _A,_B,E,I|_Z], dif(E,_A), dif(E,_B)
; Xs = [_A,_B,_C,E|_Z], Ys = [_A,_B,_C,E,I|_Z], dif(E,_A), dif(E,_B), dif(E,_C)
...

Prolog insert element after first occurrence

3 Answers3