2

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:

enter image description here

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.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • Double-recursing isn't required here. replace can simply check all the term types and deal with complex terms by recursing into itself. Just watch that you don't have the =.. case handle the list case. – Alan Baljeu May 16 '16 at 19:22
  • @AlanBaljeu Sorry, I meant double recursing as in recursing into itself. That's the step I'm unsure of. Any pointers would be much appreciated. –  May 16 '16 at 20:35

1 Answers1

5

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)).
mat
  • 40,498
  • 3
  • 51
  • 78
  • In some cases, this predicate does not replace the input pattern with the output pattern. `replace(A+B,A-B,(2+3),Result)` unifies `Result` with `2+3` instead of `2-3`. – Anderson Green Nov 04 '18 at 22:27
  • 1
    It seems to work as expected in this case, because `A+B` is not a subterm of `2+3`, is it? – mat Nov 04 '18 at 22:46
  • 1
    `replace(2, 1, T0, f(a,[[b]],g(1),X,h(z,1))).` produces only one answer, the first of several that it is required to produce by the task description in the picture. – Will Ness Nov 05 '18 at 11:49