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.