Prolog recursively replace elements of list with elements of another list

Question

Apologies for lack of clarity in title. The following is a very specific predicate I'm building, which is only partially working as intended.

% replace_elements(+SearchingElementsList,+ReplacementsList,+OriginalList,-ResultingList).
% ResultingList consists of all elements of SearchingElementsList replaced by elements of ReplacementsList respectively.

replace_elements([],[],_,_).
replace_elements([H|T],[H2|T2],[H3|T3],List) :-
    H \= H3,                                 % H is not H3, therefore
    replace_elements([H|T],[H2|T2],T3,List). % Skip this element and continue with T3.
replace_elements([H|T],[H2|T2],[H|T3],[H2|List]) :-
    replace_elements(T,T2,T3,List).          % H is found in OriginalList. Continue with tails.

Currently:

?- replace_elements([1,2,3],[one,two,three],[1,2,3,4,5],Result).
?- Result = [one,two,three|_7636].

Expected:

?- Result = [one,two,three,4,5].

Any hint would be appreciated!

Edit: Came up with a working answer for my specific problem.

% Eventually, recursion starts from all empty lists.
replace_elements([],[],[],[]).
% Rules are empty, push remaining H to List.
replace_elements([],[],[H|T],[H|List]) :-
    replace_elements([],[],T,List).
% Empty list, just go through remaining rules.
replace_elements([H|T],[H2|T2],[],List) :-
    replace_elements(T,T2,[],List).
% H < H3, move to next element in rules.
replace_elements([H|T],[H2|T2],[H3|T3],List) :-
    H < H3,
    replace_elements(T,T2,[H3|T3],List).
% H > H3, move to next element in original list.
replace_elements([H|T],[H2|T2],[H3|T3],[H3|List]) :-
    H > H3,
    replace_elements([H|T],[H2|T2],T3,List).
% Element is the same, push replacement H2 to List.
replace_elements([H|T],[H2|T2],[H|T3],[H2|List]) :-
    replace_elements(T,T2,T3,List).

Answer 1

Here is my implementation using if_/3 and extended version of memberd_t adding more list as parameters in order to achieve both checking the Searching Elements List and returning the result from ReplacementsList in one pass-traversing for efficiency:

replace_elements( [], [], _, _).
replace_elements([H|T], [H2|T1], Search_L, Replace_L):-
                if_( 
                      memberd_t(H, X, Search_L, Replace_L),
                      (
                         H2 = X,
                         replace_elements( T, T1,Search_L, Replace_L)
                      ),
                      (
                         H2 = H,
                         replace_elements( T, T1,Search_L, Replace_L)
                      )
                   ).  

memberd_t(H, X, Xs, Ys , T) :-
   i_memberd_t(Xs, Ys, H, X, T).   

i_memberd_t([], [], _, _, false).
i_memberd_t([X|Xs], [Y|Ys], E, H, T) :-
   if_( X = E, (T = true, H = Y) , i_memberd_t(Xs, Ys, E, H, T) ).

Some testcases:

?- replace_elements([1,2,3,4,5],Result,[1,2,3],[one,two,three]).
Result = [one, two, three, 4, 5].


?- replace_elements([1,2,3,4,5],Result,[1,2,3],Ts).
Result = [_792, _894, _1032, 4, 5],
Ts = [_792, _894, _1032].



?- L = [1|L1], replace_elements(L ,[one,two,three,4,5],[1,2,3],[one,two,three]).
L = [1, 2, 3, 4, 5],
L1 = [2, 3, 4, 5] ;
L = [1, 2, three, 4, 5],
L1 = [2, three, 4, 5] ;
L = [1, two, 3, 4, 5],
L1 = [two, 3, 4, 5] ;
L = [1, two, three, 4, 5],
L1 = [two, three, 4, 5].


?- replace_elements(L ,[one,two,three,4,5],[1,2,3],[one,two,three]).
L = [1, 2, 3, 4, 5] ;
L = [1, 2, three, 4, 5] ;
L = [1, two, 3, 4, 5] ;
L = [1, two, three, 4, 5] ;
L = [one, 2, 3, 4, 5] ;
L = [one, 2, three, 4, 5] ;
L = [one, two, 3, 4, 5] ;
L = [one, two, three, 4, 5].
In_L = Result, Result = [] ;
In_L = [1],
Result = [one] ;
In_L = [1, 1],
Result = [one, one] ;
In_L = [1, 1, 1],
Result = [one, one, one] ;
In_L = [1, 1, 1, 1],
Result = [one, one, one, one] ;
In_L = [1, 1, 1, 1, 1],
Result = [one, one, one, one, one] ;
In_L = [1, 1, 1, 1, 1, 1],
Result = [one, one, one, one, one, one] ;
In_L = [1, 1, 1, 1, 1, 1, 1],
Result = [one, one, one, one, one, one, one] ;
In_L = [1, 1, 1, 1, 1, 1, 1, 1],
Result = [one, one, one, one, one, one, one, one] ;
In_L = [1, 1, 1, 1, 1, 1, 1, 1, 1],
Result = [one, one, one, one, one, one, one, one, one]...and goes on....


?- replace_elements([1,2,3,4,5],Result,[1,2,X],[one,two,three]).
Result = [one, two, three, 4, 5],
X = 3 ;
Result = [one, two, 3, three, 5],
X = 4 ;
Result = [one, two, 3, 4, three],
X = 5 ;
Result = [one, two, 3, 4, 5],
dif(X, 5),
dif(X, 4),
dif(X, 3).
Result = [one, two, three, 4, 5],
L = [1, 2, 3] ;
Result = [one, two, 3, three, 5],
L = [1, 2, 4] ;
Result = [one, two, 3, 4, three],
L = [1, 2, 5] ;
Result = [one, two, 3, 4, 5],
L = [1, 2, _22546],
dif(_22546, 5),
dif(_22546, 4),
dif(_22546, 3) ;
Result = [one, three, two, 4, 5],
L = [1, 3, 2] ;...and goes on...

until finally terminates (after a lot of answers) deterministicaly

Result = [1, 2, 3, 4, 5],
L = [_23992, _23998, _24004],
dif(_23992, 5),
dif(_23992, 4),
dif(_23992, 3),
dif(_23992, 2),
dif(_23992, 1),
dif(_23998, 5),
dif(_23998, 4),
dif(_23998, 3),
dif(_23998, 2),
dif(_23998, 1),
dif(_24004, 5),
dif(_24004, 4),
dif(_24004, 3),
dif(_24004, 2),
dif(_24004, 1).


?- L=[_,_,_],replace_elements([1,2,3,4,5],[one,two,three,4,5],L,T).
L = [1, 2, 3],
T = [one, two, three] ;
L = [1, 3, 2],
T = [one, three, two] ;
L = [2, 1, 3],
T = [two, one, three] ;
L = [3, 1, 2],
T = [three, one, two] ;
L = [2, 3, 1],
T = [two, three, one] ;
L = [3, 2, 1],
T = [three, two, one] ;
false.


?- replace_elements([1,2,3,4,5],[one,two,three,4,5],Fs,Ts).
Fs = [1, 2, 3],
Ts = [one, two, three] ;
Fs = [1, 2, 3, 4],
Ts = [one, two, three, 4] ;
Fs = [1, 2, 3, 4, 5|_9700],
Ts = [one, two, three, 4, 5|_9706] ;
Fs = [1, 2, 3, 4, _10176],
Ts = [one, two, three, 4, _10218],
dif(_10176, 5) ;
Fs = [1, 2, 3, 4, _10236, 5|_10244],
Ts = [one, two, three, 4, _10284, 5|_10292],
dif(_10236, 5) ;
Fs = [1, 2, 3, 4, _10384, _10390],
Ts = [one, two, three, 4, _10432, _10438],
dif(_10384, 5),
dif(_10390, 5) ;
Fs = [1, 2, 3, 4, ...and goes on...

Answer 2

This relation can be expressed quite compactly with if_/3, =/3 and maplist/3:

:- use_module(library(apply)).   % for maplist/3

from_to_elem_repl([],[],E,E).
from_to_elem_repl([X|Xs],[Y|Ys],E,R) :-
   if_(E=X,R=Y,from_to_elem_repl(Xs,Ys,E,R)).

from_to_list_mapped(Fs,Ts,L,M) :-
   maplist(from_to_elem_repl(Fs,Ts),L,M).

The predicate from_to_elem_repl/4 describes the relation between an element and its replacement. If the element E occurs in the from-list then it's replaced by the element at the corresponding position in the to-list: Y (recursive rule). If E does not occur in the from-list it is not replaced (base case). The predicate from_to_list_mapped/4 uses maplist/3 to map the predicate from_to_elem_repl/4 to the list L thus yielding the list with the replacements M. Your example query succeeds deterministically:

?- from_to_list_mapped([1,2,3],[one,two,three],[1,2,3,4,5],M).
M = [one, two, three, 4, 5].

In the other direction all eight solutions are found:

?- from_to_list_mapped([1,2,3],[one,two,three],L [one,two,three,4,5]).
L = [1, 2, 3, 4, 5] ;
L = [1, 2, three, 4, 5] ;
L = [1, two, 3, 4, 5] ;
L = [1, two, three, 4, 5] ;
L = [one, 2, 3, 4, 5] ;
L = [one, 2, three, 4, 5] ;
L = [one, two, 3, 4, 5] ;
L = [one, two, three, 4, 5].

You could also ask for possible mapping pairs for a given list and its replacement:

?- from_to_list_mapped(Fs,Ts,[1,2,3,4,5],[one,two,three,4,5]).
Fs = [1, 2, 3],
Ts = [one, two, three] ;
Fs = [1, 2, 3, 4],
Ts = [one, two, three, 4] ;
Fs = [1, 2, 3, 4, 5|_G5111],
Ts = [one, two, three, 4, 5|_G5114] ;
Fs = [1, 2, 3, 4, _G5258],
Ts = [one, two, three, 4, _G5279],
dif(_G5258, 5) ;
Fs = [1, 2, 3, 4, _G5275, 5|_G5279],
Ts = [one, two, three, 4, _G5299, 5|_G5303],
dif(_G5275, 5) ;
Fs = [1, 2, 3, 4, _G5316, _G5319],
Ts = [one, two, three, 4, _G5340, _G5343],
dif(_G5316, 5),
dif(_G5319, 5) ;
Fs = [1, 2, 3, 4, _G5333, _G5336, 5|_G5340],
Ts = [one, two, three, 4, _G5360, _G5363, 5|_G5367],
dif(_G5333, 5),
dif(_G5336, 5) ;
.
.
.

Obviously there are infinitely many possibilities. But if you ask for a fixed length, the predicate terminates:

?- Fs=[_,_,_],from_to_list_mapped(Fs,Ts,[1,2,3,4,5],[one,two,three,4,5]).
Fs = [1, 2, 3],
Ts = [one, two, three] ;
Fs = [1, 3, 2],
Ts = [one, three, two] ;
Fs = [2, 1, 3],
Ts = [two, one, three] ;
Fs = [3, 1, 2],
Ts = [three, one, two] ;
Fs = [2, 3, 1],
Ts = [two, three, one] ;
Fs = [3, 2, 1],
Ts = [three, two, one] ;
false.

You can also ask for a mapping without specifying the replacement elements:

?- from_to_list_mapped([1,2,3],Ts,[1,2,3,4,5],R).
Ts = [_G4920, _G4937, _G4965],
R = [_G4920, _G4937, _G4965, 4, 5].

As you see the predicate is quite versatile. Play around with it to find other possible uses.