Prolog рекурсивно заменяет элементы списка элементами другого списка

Ответ 1

Вот моя реализация, использующая 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...

Ответ 2

Я дам мыслительный процесс для решения проблемы. Пара принципов:

• Мышление реляционно, а не императивно
• Верхний дизайн

Вы хотите:

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

Возможное улучшение вышеприведенной реализации, чтобы сделать ее более реляционной, избегая конструкцию ->/;, мы можем определить не членство реляционно, используя 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)
...

Ответ 3

Это отношение можно выразить довольно компактно с помощью 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 встречается в списке, то он заменяется элементом в соответствующей позиции в списке: Y (рекурсивное правило). Если E не встречается в списке, он не заменяется (базовый регистр). Предикат 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].

Как вы видите, предикат довольно универсален. Играйте с ним, чтобы найти другие возможные варианты использования.