Next: Building Structure in Up: List Processing Previous: Return a Result

## Reconstructing Lists

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([H1T1],[H2T2]). 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([],[]).

triple([H1T1],T2):-

H2 is 3*H1,

triple(T1,[H2T2]).

```
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).
```
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],[3X]) is true

```
Even if triple([2],[3X]) 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.

Next: Building Structure in Up: List Processing Previous: Return a Result

Paul Brna
Mon May 24 20:14:48 BST 1999