0

I am getting a hard time figuring out how to replace some leaves in a Prolog tree constant. So e.g. substitute(a(b,c,d,f(c,d,e),c),X) should replace all c in the tree and the output should be like X=a(b,xyz,d,f(xyz,d,e),xyz).

I tried and got somewhat a shallow predicate

substitute(X,Y):- X =..A  , myfun(A,Z), Y=..Z .
myfun([],[]).
myfun([c|T],[xyz|Z]):- myfun(T,Z), !.
myfun([H|T], [H|Z]):-  myfun(T,Z).

So what this code achieves is, for input substitute(a(b,c,d,f(c,d,e),c),X) it gives X=a(b,xyz,d,f(c,d,e),xyz). But i want it to be deep. Any help is much appreciated.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Harsh Shah
  • 368
  • 3
  • 17

1 Answers1

1

You might want to change the last clause minimally to make it "deep".

myfun([H|T], [HX|Z]) :- substitute(H,HX), myfun(T,Z).

Edit 1: If you want only "leaves" to be substituted then refine your first clause as below.

substitute(c,xyz) :- !.
substitute(X,X) :- X =.. [_], !.
substitute(X,Y) :- X =.. [F|A], myfun(A,Z), Y =.. [F|Z]. /* functor not a leaf */

Edit 2: Oops. Fixed a bug in Edit 1. (Thanks Will Ness. Should have tried my code...) Now it seems to do what I expect it to:

?- substitute(a,X).
X = a.

?- substitute(c,X).
X = xyz.

?- substitute(f(a,b,c),X).
X = f(a, b, xyz).

?- substitute(a(b,c,d,f(c,d,e),c),X).
X = a(b, xyz, d, f(xyz, d, e), xyz).

?- substitute(c(c),X).
X = c(xyz).

(Note: The clause myfun([c|T],[xyz|Z]):- myfun(T,Z), !. is no longer needed.)

halfbit
  • 3,414
  • 1
  • 20
  • 26
  • I also thought of calling substitute(H,HX) from myfun similarly, but then my prolog panics ie it tells me Exceeding addressable memory. – Harsh Shah Nov 17 '13 at 22:18
  • Yes, if you do not use edit 1 you get into infinite recursion then for e.g. for `substitute(a).`. Sorry I didn't try it before posting. – halfbit Nov 17 '13 at 22:26
  • Wonderful. It does work now. can you just explain the rule substitute(X,X) :- X =.. [_], !. , I got the other rules! – Harsh Shah Nov 17 '13 at 22:28
  • The rule `substitute(X,X) :- X =.. [_], !.` keeps solitary symbols a like in `substitute(a,a)`. `X =.. [_]` matches `a =.. [a]`. The underscore means that we do not care about the actual symbol in `X`. (Due to the cut in the clause before we know it is not `c`.) – halfbit Nov 17 '13 at 22:40
  • oh great! Now i get it! Thank You! – Harsh Shah Nov 17 '13 at 23:00