CODEWITHSUNDEEP
prolog
igla
igla

Reputation: 11

Prolog replace all occurrences of an element by another element in a Tree

A binary tree is defined as follows:

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

I have to write a predicate replace(X,Y,OldTree,NewTree) that replaces all occurrences of X by Y. I have managed to write this so far but I think it's wrong :

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

Any help would be greatly appreciated!

Upvotes: 1

Views: 511

Answers (1)

false
false

Reputation: 10120

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

This replaces one element using library(reif) for SICStus or SWI.

Now we need to replace all elements, so we will apply replacement/4 a couple of times. Some part will remain the same, and some of it will change. In fact, the first two arguments will always be the same, only the last two change. So we could write call(replacement(X,Y), TX, TY). In fact, we could now define that relation over the trees independently of our concrete replacement-relation:

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

Upvotes: 1

Related Questions