Пролог заменяет все вхождения элемента другим элементом в дереве

Question

Двоичное дерево определяется следующим образом:

tree(-). % empty tree.
tree(n(X,L,R)) :- tree(L), tree(R). 

Я должен написать предикат replace(X,Y,OldTree,NewTree), который заменяет все вхождения X на Y. Мне уже удалось написать это, но я думаю, что это неправильно:

replace(_,_,n,n).
replace(Old,New,n(X,L,R),n(X,L1,R1)) :-
    replace(Old,New,L,L1),
    replace(Old,New,R,R1).

Любая помощь будет принята с благодарностью!

Answer 1

replacement(X, Y, TX, TY) :-
   if_(X = TX, Y = TY, TX = TY).

Это заменяет один элемент, используя library(reif) для SICStus или SWI .

Теперь нам нужно заменить все элементы, поэтому мы будем применять replacement/4 пару раз. Некоторая часть останется прежней, а часть изменится. На самом деле, первые два аргумента всегда будут одинаковыми, только последние два изменятся. Таким образом, мы могли бы написать call(replacement(X,Y), TX, TY). Фактически, теперь мы можем определить это отношение по деревьям независимо от нашего конкретного отношения замены:

maptree(_R_2, n, n).
maptree(R_2, n(TX, L0, R0), n(TY, L, R)) :-
   call(R_2, TX, TY),
   maptree(R_2, L0, L),
   maptree(R_2, R0, R).

replace(X, Y, TX, TY) :-
   maptree(replacement(X,Y), TX, TY).