Prolog递归地用另一个列表的元素替换list的元素

Question

对标题不清晰表示歉意.以下是我正在构建的一个非常具体的谓词,它只是部分按预期工作.

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

目前:

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

预期:

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

任何提示将不胜感激!

编辑:为我的具体问题提出了一个有效的答案.

% 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

使用if_/3,=/3和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).

谓词from_to_elem_repl/4描述了元素与其替换之间的关系.如果元素E出现在from-list中,那么它将被to-list中相应位置的元素替换:( Y递归规则).如果E在from-list中没有出现,则不会被替换(基本情况).谓词from_to_list_mapped/4使用maplist/3将谓词from_to_elem_repl/4映射到列表,L从而产生具有替换的列表M.您的示例查询确定性地成功:

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

在另一个方向,找到了所有八种解决方案:

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

您还可以询问给定列表及其替换的可能映射对:

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

显然,存在无限多种可能性.但是如果你要求一个固定长度,谓词就会终止:

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

您也可以在不指定替换元素的情况下请求映射:

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

如你所见,谓词非常通用.玩它来寻找其他可能的用途.

Answer 2

这是我的实现使用if_/3和扩展版本memberd_t添加更多列表作为参数,以实现检查搜索元素列表和从R eplacementsList返回结果一次遍历遍历效率:

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

一些测试用例:

?- 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 3

我将提供解决问题的思考过程.一些原则是:

• 从关系而非强制性思考
• 自上而下的设计

你要:

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

我会稍微重命名一下,以免它变得势在必行:

translated_list(Trans1, Trans2, List1, List2).

我删除了+,-因为理想情况下,我们希望这是一般关系.这是一个关系,在相应的元件List1和List2经由在对应的元件限定的"转换表"彼此相关的Trans1和Trans2.

在Prolog中,当考虑相应的列表元素时,这让我立刻想到使用类似的东西maplist.此外,处理两个独立列表以定义术语之间的1-1关系是尴尬的.使用具有看起来像的单个转换表更简单,更清晰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).

现在我们需要一个trans_table提供转换表元素之间关系的谓词.这种关系表明转换表E1-E2中的元素是相应的单个元素所在的位置E1和E2:

trans_table_element(E1, E2, E1-E2).

我们需要一个使用转换表描述两个相应元素的谓词.

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

从这里,你得到:

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

以及:

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

和

| ?- 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,_] ? ;

...

如果您想在规则中强制执行转换表仅在不同元素之间进行转换,那么您可以定义:

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

然后你会得到(这次使用SWI Prolog):

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

通过避免->/ ;construct,可以改进上述实现以使其更具关系性,我们可以使用关系定义非成员关系maplist.

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

除上述结果外,收益率:

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