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

One issue is that your base case uses anonymous variables (`_`) in places you should have a specific value or regular variable. In other words, `replace_elements([], [], _, _)` says that when you replace the elements in an empty list with elements in another empty list, you can get anything you want from anything you want (!), which isn't logical. Think about what your base case means and restate it. In Prolog, different anonymous variables are different. In this case, you most certainly don't want them anonymous. — lurker, Nov 16 '17 at 14:53
Also, consider what happens with `replace_elements([1,2,3], [one,two,three], [3,1,5,2,1,4,3], Result).` — lurker, Nov 16 '17 at 14:56
`(<)/2` and `(>)/2` are arithmetical comparisons, whereas equality is syntactical — false, Nov 18 '17 at 19:47

coder · Accepted Answer · 2017-11-20T10:13:26.507

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

score 7 · Answer 2 · answered Nov 17 '17 at 21:41

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.

lurker · Answer 3 · 2017-11-27T12:14:16.583

I'll provide a thought process for solving the problem. A couple of principles would be:

Thinking relationally rather than imperatively
Top down design

You want:

replace_elements(+SearchingElementsList, +ReplacementsList, +OriginalList, -ResultingList).

I'll rename it a little to make it not be as imperative:

translated_list(Trans1, Trans2, List1, List2).

I removed the + and - because, ideally, we'd like this to be as general a relation as possible. This is a relation that the corresponding elements in List1 and List2 are related to each other via the "translation table" defined by corresponding elements in Trans1 and Trans2.

In Prolog, when considering corresponding list elements, that makes me immediately think of using something like maplist. Also, it's awkward handling two independent lists to define a 1-1 relationship between terms. It is easier and cleaner to use a single translation table with elements that look like, say, t1-t2.

translated_list(Trans1, Trans2, List1, List2) :-
    % TransTable is a translation table consisting of t1-t2 pairs from Trans1 and Trans2
    maplist(trans_table_element, Trans1, Trans2, TransTable),

    % List1 and List2 are related using the translation table, TransTable
    maplist(corresponding_element(TransTable), List1, List2).

Now we need a predicate trans_table that provides a relationship between translation table elements. This relation says that an element in the translation table is E1-E2 where the corresponding individual elements are E1 and E2:

trans_table_element(E1, E2, E1-E2).

And we need a predicate that describes two corresponding elements using a translation table.

corresponding_element(TransTable, E1, E2) :-
(    member(E1-E2, TransTable)
->   true            % Translation exists
;    E1 = E2         % Translation doesn't exist
).

From this, you get:

| ?- translated_list([1,2,3], [one, two, three], [4,1,3,5,2,1,3], L).

L = [4,one,three,5,two,one,three]

yes
| ?-

As well as:

| ?- translated_list([1,2,3], [one, two, three], L, [4,one,three,5,two,one,three]).

L = [4,1,3,5,2,1,3] ? a

no

And

| ?- translated_list(A, B, [4,1,3,5,2,1,3], [4,one,three,5,two,one,three]).

A = [4,1,3,5,2]
B = [4,one,three,5,two] ? ;

A = [4,1,3,5,2,_]
B = [4,one,three,5,two,_] ? ;

...

If you want to enforce in your rules that the translation table only translates between different elements, then you could define:

trans_table_element(E1, E2, E1-E2) :- dif(E1, E2).

And then you'd get (using SWI Prolog this time):

2 ?-  translated_list(A, B, [4,1,3,5,2,1,3], [4,one,three,5,two,one,three]).
A = [1, 3, 2],
B = [one, three, two] ;
A = [1, 3, 2, _1240],
B = [one, three, two, _1276],
dif(_1240, _1276) ;
A = [1, 3, 2, _1492, _1498],
B = [one, three, two, _1534, _1540],
dif(_1492, _1534),
dif(_1498, _1540) ;
...

UPDATE

A possible improvement in the above implementation to make it more relational by avoiding the ->/; construct, we can define non-membership relationally using maplist.

corresponding_element(TransTable, E1, E2) :-
    member(E1-E2, TransTable).
corresponding_element(TransTable, E1, E2) :-
    maplist(dif(E1-E2), TransTable),
    E1 = E2.

In addition to the above results, yields:

6 ?- translated_list([1,2,3],Ts,[1,2,3,4,5],R).
Ts = [_9016, _9034, _9052],
R = [_9016, _9034, _9052, 4, 5] ;
Ts = [_9640, _9646, _9652],
R = [_9640, _9646, 3, 4, 5],
dif(3, _9652) ;
Ts = [_9640, _9646, _9652],
R = [_9640, 2, _9652, 4, 5],
dif(2, _9646) ;
Ts = [_9856, _9862, _9868],
R = [_9856, 2, 3, 4, 5],
dif(2, _9862),
dif(3, _9868)
...

How can `( member(E1-E2, TransTable) -> ` be understood relationally? — false, Nov 17 '17 at 22:56
Alternatively, you could have used some safe member. Like `( setof(E1-E2, member(E1-E2, Transtable), Rs), ( Rs = [_,_|_] -> instantiation_error ; true ) ->`. — false, Nov 18 '17 at 19:43
@false thank you for that suggest. Those are the sorts of clever things I often don't think of with Prolog problems such as these. — lurker, Nov 18 '17 at 22:05
@false I suppose one could start simple, one small predicate at a time. Do we need a more safe or relational if-then-else? `if_/3` comes up a lot as a solution. Is it in the library? If not, is it not an adequate enough solution? — lurker, Nov 18 '17 at 22:23
Some are [here](http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/). Still not clear to me how to proceed: Many separate tiny libraries, or some way to put them all into one. — false, Nov 18 '17 at 22:38
`( ( call_nth( member(E1-E2, Translatable), Nth), Nth >= 2 -> instantiation_error ; member(E1-E2, Translatable ) ->` may be even more efficient - no need to explore the entire list. — false, Nov 18 '17 at 23:47
... actually some more tests would be needed. Think of `Translatable = [t-v,-t-v], member(t-v,Translatable)` there, an instantiation error is not appropriate — false, Nov 19 '17 at 00:28
@false yes, there are many assumptions in the problem, such as that the original two "translation" tables are the same length and that the elements are all unique (the translation table forms a bijection), etc. — lurker, Nov 19 '17 at 02:11

Prolog recursively replace elements of list with elements of another list

3 Answers3