Пролог: замена элемента в списке с другим списком

Question

Для следующего запроса (и предикатов, определенных в следующем), я получаю неожиданный ответ:

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

Первый результат является один я хочу. Второй, который я не хочу ...

Как предотвратить второй? Возможно, добавив ! где-нибудь?

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

Answer 1

редактировать

это становится волосатый, и мой ответ не приходилось именно по просьбе ... так что давайте посмотрим код с минимальным изменения:

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

разрез просто фиксирует второе предложение ...

резюме старый ответить

ваш CONCAT/3 такая же, как хорошо известный Append/3, поэтому рассмотрим этот подход

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. 

редактировать

по просьбе комментариев, это расширение обрабатывает список Элемент, подходящий для изменения, с простым сопоставлением рисунка (примечание: добавить до предыдущего пункта)

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

тест

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

редактировать

я не заметил, что если элемент не найден он не должен терпеть неудачу ... последний «всеобъемлющая» положение может обрабатывать этот случай:

repl(ListOrig, _Element, _Replace, ListOrig). 

или лучше распространить оригинал как

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

Answer 2

Чтобы разрешить для нескольких матчей в списке, используйте meta-predicatemaplist/3 и действуйте следующим образом:

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

Примеры запросов:

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

Answer 3

Как @repeat уже хорошо показано, следует использовать ограничение dif/2, чтобы описать, что два термина отличаются. Это позволяет избежать неожиданного и неправильного второго решения.

Кроме того, как всегда при описании списков, а также рассмотреть возможность использования dcg обозначения: Вы можете использовать нетерминальные list//1 сделать декларативно описать список таким образом, что она может быть легко и эффективно сращены в другие списки на конкретных позициях.

Рассмотрим:

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

Мы используем интерфейс предикат phrase/2 использовать DCG. Например:

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

Это истинное отношение, которое работает во всех направлениях. Он может ответить на довольно общие вопросы, такие как: Какой товар был заменен другим списком? Пример:

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