CODEWITHSUNDEEP
listprolog
Dizeme
Dizeme

Reputation: 57

Prolog insert element after first occurrence

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!

Upvotes: 1

Views: 448

Answers (3)

repeat
repeat

Reputation: 18726

Let's keep it simple and use append/3, maplist/2 and 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)
...

Upvotes: 1

repeat
repeat

Reputation: 18726

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

Upvotes: 2

lurker
lurker

Reputation: 58244

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.

Upvotes: 1

Related Questions