Prolog: replacing an element in a list with another list

Question

For the following query (and the predicates defined in the following) I get an unexpected answer:

?- rep([1,2,3], 3, [2,3,4], L).
L = [1, 2, 2, 3, 4] ;
L = [1, 2, 3].                           % unexpected answer

The first result is the one I want. The second one I do not want...

How can I prevent the second one? Probably by adding ! somewhere?

concat([], L, L).
concat([H|T], L, [H|Res]) :-
   concat(T, L, Res).

repl([], _, _, []).
repl([Val|T], Val, Repl, Res) :-
   repl(T, Val, Repl, Temp),
   concat(Repl, Temp, Res).
repl([H|T], Val, Repl, [H|Res]) :-
   repl(T, Val, Repl, Res).

the cut should go after concat/3 call: `concat(Repl, Temp, Res), !.` — CapelliC, Dec 22 '15 at 12:56
@CapelliC. Not steadfast! **If** we are to use cut, then we better do it like this: `repl([Val|T], Val, Repl, Res) :- !, concat(Repl, Temp, Res), repl(T, Val, Repl, Temp).` — repeat, Dec 22 '15 at 13:01
Please be more specific! What answer(s) do you expect for `?- repl([x,y,x,y,x],x,[x,y,x],L).` — repeat, Dec 22 '15 at 13:06

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

To allow for multiple matches per list, use meta-predicate maplist/3 and proceed like this:

item_replacement_item_mapped(E, Es, E, Es).
item_replacement_item_mapped(X,  _, E, [E]) :-
   dif(X, E).

repl(Es0,X,Xs,Es) :-
   maplist(item_replacement_item_mapped(X,Xs), Es0, Ess1),
   append(Ess1, Es).

Sample queries:

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

?- repl([x,y,x,y,x], x, [x,y,x], L).
   L = [x,y,x,y,x,y,x,y,x,y,x]
;  false.

score 2 · Answer 2 · answered Dec 22 '15 at 13:19

As @repeat has already nicely shown, you should use the constraint dif/2 to describe that two terms are different. This avoids the unexpected and wrong second solution.

In addition, as always when describing lists, also consider using dcg notation: You can use the nonterminal list//1 do declaratively describe a list in such a way that it can be easily and efficiently spliced into other lists at specific positions.

Consider:

replacement([], _, _) --> [].
replacement([L|Ls], L, Rs) -->
    list(Rs),
    replacement(Ls, L, Rs).
replacement([L|Ls], R, Rs) --> [L],
    { dif(L, R) },
    replacement(Ls, R, Rs).

list([]) --> [].
list([L|Ls]) --> [L], list(Ls).

We use the interface predicate phrase/2 to use the DCG. For example:

?- phrase(replacement([1,2,3], 3, [2,3,4]), Ls).
Ls = [1, 2, 2, 3, 4] ;
false.

It is a true relation that works in all directions. It can answer quite general questions, such as: Which item has been replaced by another list? Example:

?- phrase(replacement([1,2,3], E, [2,3,4]), [1,2,2,3,4]).
E = 3 ;
false.

CapelliC · Answer 3 · 2015-12-22T16:57:27.250

0

edit

this is getting hairy, and my answer didn't accounted precisely for request... so let's see your code with minimal change:

concat([], L, L).
concat([H|T], L, [H|Res]) :-
   concat(T, L, Res).

repl([], _, _, []).
repl([Val|T], Val, Repl, Res) :- !, % as noted by @repeat, better to commit early...
   repl(T, Val, Repl, Temp),
   concat(Repl, Temp, Res). % !.
repl([H|T], Val, Repl, [H|Res]) :-
   repl(T, Val, Repl, Res).

the cut simply commits the second clause...

resume old answer

your concat/3 is the same as the well known append/3, so consider this approach

repl(ListOrig, Element, Replace, ListUpdated) :-
      append(H, [Element|T], ListOrig),
      append(H, Replace, Temp),
      append(Temp, T, ListUpdated).

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

edit

as requested by comments, this extension handles a list of Element to match for change, with simple pattern matching (note: add before the previous clause)

repl(ListOrig, [], _Replace, ListOrig).
repl(ListOrig, [E|Es], Replace, ListUpdated) :-
    repl(ListOrig, E, Replace, Temp),
    repl(Temp, Es, Replace, ListUpdated).

test

?- repl([1,2,3],[2,3],[x,y,z],R).
R = [1, x, y, z, x, y, z] ;
false.

edit

I didn't noticed that if Element is not found it should not fail... a last 'catchall' clause could handle this case:

repl(ListOrig, _Element, _Replace, ListOrig).

or better, extend the original like

repl(ListOrig, Element, Replace, ListUpdated) :-
      (  append(H, [Element|T], ListOrig)
      -> append(H, Replace, Temp),
         append(Temp, T, ListUpdated)
      ;  ListOrig = ListUpdated
      ).

edited Dec 22 '15 at 16:57

answered Dec 22 '15 at 10:45

CapelliC

59,646
5
47
90

Could you please tell us what modifications should be added if Element becomes a list (LElement) with the idea to repeat the "repl" predicate for each element of LElement? Thanks – Hana Dec 22 '15 at 11:18
You should specify then if successive repl/4 operate on previous results **or** each one creates its own copy. Which of these two behaviours ? – CapelliC Dec 22 '15 at 12:24
Operates in previous results. – Hana Dec 22 '15 at 12:42
How about running `?- repl([x,y,x,y,x], x, [x,y,x], L).` – repeat Dec 22 '15 at 13:04
1

The cut makes your program lose steadfastness! As a consequence the goal `repl([1, 2, 3], 3, [2, 3, 4], [1,2,3])` succeeds even though it should fail. – repeat Dec 22 '15 at 13:36
@repeat: ok, thanks for the sample... I see it doesn't enforce steadfastness... it just remove the unwanted second solution. For this pattern, adding the cut after the `:-` is better. – CapelliC Dec 22 '15 at 13:44
I beg to differ. IMO adding a cut as a kind of "commit if above goals succeed" is an antipattern because it jeopardizes steadfastness. All it takes is a single "output-unification" in any goal before the cut and steadfastness is gone. – repeat Dec 22 '15 at 16:53
@repeat: you're right. The proper place is where you indicated in your comments. Otoh, OP's original code is not steadfast anyway... – CapelliC Dec 22 '15 at 16:56
@CapelliC : could you consider this new specification. /*We define disjoint groups of individuals*/ group([i1, i3, i4]). group ([i7, i5, i9]). /*By using the previous repl predicate, how now to replace in a ListOrig each element belonging to a group by all his group members? Example */ If we have ListOrig = [i10, i1, i5, i11], we should return [i10, i1, i3, i4, i7, i5, i9, i11] 2 additional options : in a sub-list format : [i10, [i1, i3, i4], [i7, i5, i9], i11] and/or all the possible permutations of individuals inside a group. – Hana Dec 24 '15 at 17:30
@repeat : could you consider this new specification. /*We define disjoint groups of individuals*/ group([i1, i3, i4]). group ([i7, i5, i9]). /*By using the previous repl predicate, how now to replace in a ListOrig each element belonging to a group by all his group members? Example */ If we have ListOrig = [i10, i1, i5, i11], we should return [i10, i1, i3, i4, i7, i5, i9, i11] 2 additional options : in a sub-list format : [i10, [i1, i3, i4], [i7, i5, i9], i11] and/or all the possible permutations of individuals inside a group. – Hana Dec 27 '15 at 06:48

Prolog: replacing an element in a list with another list

3 Answers3