CODEWITHSUNDEEP
replaceprologexpression
user3026485
user3026485

Reputation: 79

replacing multiple terms from a list in prolog

I have defined a predicate replace(word_to_be_replaced, replacement, [List_requires_replacement], [storing_List] ) and i am using it to simplify arithmetic expressions like:-

simplify([Head|Tail], Simplified) :-
   (replace(add(a,a), 2*a, [Head|Tail], L) ; L = [Head|Tail]), !, Simplified = L.

now the problem is i'd like to replace terms likex+y+x by 2*x+y too. The arithmetic expression that the user inputs will be of the following form example add(x,div(1,z)) please help as soon as possible. Thank you.

Upvotes: 3

Views: 205

Answers (1)

Daniel Lyons
Daniel Lyons

Reputation: 22803

You need to normalize your terms somehow. This is a highly incomplete sketch of how I'd be tempted to approach it. I think the approach could be borne out, but you will need to do a lot of double-checking that it handles every case correctly.

First, notice how it looks in canonical form:

?- write_canonical(x+y+x).
+(+(x,y),x)
true.

There's the crux of the problem. One x is deep inside the tree. The other is up on a different level. We need to get them all in the same place so we can process them together. This means we want to move them out into the same list somehow. I think we want [+, x, y, x] because then we can sort that into [+, x, x, y] and then process it recursively.

?- x+y+x =.. Q.
Q = [+, x+y, x].

Better, but not all the way there yet.

expand(Var, Var) :- number(Var) ; atom(Var).
expand(Term, Expanded) :-
  (\+ number(Var), \+ atom(Var)),
  Term =.. Parts, 
  maplist(expand, Parts, Expanded).

?- expand(x+y+x, Q).
Q = [+, [+, x, y], x] ;

Better. Now we need to flatten it somehow.

flatten_expr([Op, [Op|Inner] | Outer], Result) :- 
  append([Op|Inner], Outer, Result).
flatten_expr(Other, Other).

?- expand(x+y+x, Q), flatten_expr(Q, QFlat).
Q = [+, [+, x, y], x],
QFlat = [+, x, y, x]

If we sort in the middle we can just get on with life.

flatten_expr([Op, [Op|Inner] | Outer], Result) :- 
  append([Op|Inner], Outer, ResultU), 
  msort(ResultU, Result).
flatten_expr(A, A).

Now you can apply your patterns to these and simplify.

simplify([+, X, X | Rest0], [+, [*, 2, X] | Rest1]) :- 
  simplify([+, Rest0], [+, Rest1]).

?- expand(x+y+x, Q), flatten_expr(Q, QFlat), simplify(QFlat, Simplified).
Q = [+, [+, x, y], x],
QFlat = [+, x, x, y],
Simplified = [+, [*, 2, x], y]

Then you just need a way to convert back to the algebraic representation. If expand/2 were a little better, perhaps it could be run backwards to do that, but this one isn't. I leave this as an exercise for the student.

Upvotes: 2

Related Questions