recursion - Prolog - replacing subterms

Question

I'm doing some past exam papers for practice for my exam, and I've come across a question that I'm not quite sure how to tackle:

I know I've got to use the "univ" function to break up the term into a list, and then recurse through that list and check if any of the elements in the list equal the term we want to replace. However, I'm a bit lost with double recursing when the list contains another complex term that we have to break down further. My attempt so far is as follows:

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.

Any pointers would be much appreciated. Note that for the exam we can't use external modules.

Thanks for your time.

Answer 1

The key to such tasks is to recognize which cases you actually need to distinguish.

As it turns out: Not many.

For example:

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

I have taken the small liberty to use an argument order that makes maplist/3 applicable.

To quote from the Prolog standard:

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

For this reason, atomic and complex terms can be handled uniformly in this case! There is no reason to distinguish between atomic and complex terms, nor is there any reason to treat lists specially in any way.

Example:

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