We now elaborate on a feature of the schema for
return a result ---having processed all elements.
Looking at the structure of the head of the 2nd clause for triple/2
we see that the recursive call is structurally simpler than the head of the clause --- viz
triple(T1
T2) is `simpler' than triple([H1
T1]
[H2
T2]).
The input variable for the recursive call
a list
is structurally smaller
and so is the output variable.
Many students try to write triple/2 as:
triple([] []).This does not work at all. Looking at the trace output it is tempting to think the program is nearly right. Consider this trace output from SICStus Prolog for the goal triple([1 2] X).triple([H1
T1] T2):-
H2 is 3*H1
triple(T1 [H2
T2]).
1 1 Call: triple([1 2] _95) ?2 2 Call: _229 is 3*1 ?
2 2 Exit: 3 is 3*1 ?
3 2 Call: triple([2] [3
_95]) ?
4 3 Call: _520 is 3*2 ?
4 3 Exit: 6 is 3*2 ?
5 3 Call: triple([] [6 3
_95]) ?
5 3 Fail: triple([] [6 3
_95]) ?
4 3 Redo: 6 is 3*2 ?
4 3 Fail: _520 is 3*2 ?
3 2 Fail: triple([2] [3
_95]) ?
2 2 Redo: 3 is 3*1 ?
2 2 Fail: _229 is 3*1 ?
1 1 Fail: triple([1 2] _95) ?
At one point
we have a term triple([]
[6
3
_95]) which
if only
it succeeded
might provide the result we want (even though it seems to be back to front).
The first observation is that
since its first argument is [] it can only match the first
clause for triple and this has a second argument of [] ---so
this call must fail.
The second observation is that each recursive call is called with an increasingly complex
second argument ---but
when the call is over
there is no way in which this complex argument
can be passed back to the original query. For example
we start by trying to show that
triple([1 2] X) is true if triple([2] [3Even if triple([2] [3X]) is true
X]) were true
that only means that triple([1
2]
X)
is true ---where has the 3 gone?
We now describe the original schema for return a result ---having processed all elements and an alternative way.