replace - 替换序言列表中的多个术语

Question

我定义了一个谓词 replace(word_to_be_replaced, replacement, [List_requires_replacement], [storing_List] ) 我用它来简化算术表达式，例如:-

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

现在的问题是我也想用 2*x+y 替换像 x+y+x 这样的术语。用户输入的算术表达式将具有以下形式示例 add(x,div(1,z)) 请尽快提供帮助。谢谢。

Answer 1

您需要以某种方式规范化您的条款。这是一个非常不完整的草图，说明了我会如何处理它。我认为该方法可以得到证实，但您需要进行大量复核以确保它能正确处理每种情况。

首先，请注意它在规范形式下的样子:

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

这就是问题的症结所在。一个 x 在树的深处。另一个在不同的层次上。我们需要将它们全部放在同一个地方，以便我们可以一起处理它们。这意味着我们想以某种方式将它们移到同一个列表中。我认为我们需要 [+, x, y, x] 因为这样我们就可以将其排序为 [+, x, x, y] 然后递归处理它。

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

好多了，但还没有完全好。

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] ;

更好。现在我们需要以某种方式将其展平。

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]

如果我们在中间排序，我们就可以继续生活。

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

现在您可以将您的模式应用于这些并简化。

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]

然后你只需要一种方法来转换回代数表示。如果 expand/2 稍微好一点，也许它可以向后运行来做到这一点，但这个不是。我将此留作学生的练习。