recursion - Prolog - 替换子项

Question

我正在做一些过去的试卷来练习考试，我遇到了一个不太确定如何解决的问题:

我知道我必须使用“univ”函数将术语分解为列表，然后递归该列表并检查列表中的任何元素是否等于我们要替换的术语。然而，当列表包含另一个我们必须进一步分解的复杂术语时，我对双重递归有点迷失。到目前为止我的尝试如下:

complexTerm(X) :- nonvar(X), functor(X, _, A), A > 0.

replace(Term, Subterm, Subterm1, Term1) :-
    Term =.. [H|T],
    replaceSub([H|T], Subterm, Subterm1, Term1)

replaceSub([], Subterm, Subterm1, Term1).
replaceSub([H], Subterm, Subterm1, Term1) :- 
    atomic(X),
    H == Subterm, 
    H = Subterm1.
replaceSub([H], Subterm, Subterm1, Term1) :-
    complexTerm(H),
    replace(H, Subterm, Subterm1, Term1).
replaceSub([H|T]) :- % not sure where to continue with this.

任何指示将不胜感激。请注意，对于考试，我们不能使用外部模块。

感谢您的宝贵时间。

Answer 1

此类任务的关键是识别您实际上需要区分哪些情况。

事实证明:并不多。

例如:

replace(Subterm0, Subterm, Term0, Term) :-
        (   Term0 == Subterm0 -> Term = Subterm
        ;   var(Term0) -> Term = Term0
        ;   Term0 =.. [F|Args0],
            maplist(replace(Subterm0,Subterm), Args0, Args),
            Term =.. [F|Args]
        ).

我稍微自由地使用了使 maplist/3 适用的参数顺序。

引用 Prolog 标准:

8.5.3 (=..)/2 - univ

8.5.3.1 Description

'=..'(Term, List) is true iff:

  - Term is an atomic term and List is the list whose
  only element is Term, or
  ...

因此，在这种情况下，可以统一处理原子术语和复杂术语!没有理由区分原子术语和复杂术语，也没有任何理由以任何方式特殊对待列表。

示例:

?- replace(1, 2, f(a,[[b]],g(1),X,h(z,1)), T).
T = f(a, [[b]], g(2), X, h(z, 2)).