We want to `glue', say, ** [a,b]** to ** [c,d,e]** to give the result
** [a,b,c,d,e]**.
That is, we want a predicate ** append/3** taking two lists as input and
returning the third argument as the required result.

Here are the two lists as trees:

You might think of checking to see whether ** cons([a,b],[c,d,e])**
correctly represents the list ** [a,b,c,d,e]**.
Look at this `solution' as a tree.

It is not the required

Let's try again:

We could solve our problem in a procedural manner using our list deconstructor as follows:

Lop off the headaof the first list[a,b]Solve the subproblem of gluing

[b]to[c,d,e]Put the head

aback at the front of the resultBut we have a subproblem to solve:

Lop off the head

bof the first list[b]Solve the subproblem of gluing

[]to[c,d,e]Put the head

aback at the front of the resultBut we have a subproblem to solve:

Gluing

[]to[c,d,e]is easy..the result is[c,d,e]

First thing to note is that there is a recursive process going on. It can be read as:

Take the head off the first list and keep it until we have solved the subproblem of gluing the rest of the first list to the second list. To solve the subproblem simply apply the same method.Once we are reduced to adding the empty list to the second list, return the solution ---which is the second list. Now, as the recursion unwinds, the lopped off heads are stuck back on in the correct order.

Here is the code:

append([],List2,List2).append([HeadList1],List2,[HeadList3]):-

append(List1,List2,List3).

Mon May 24 20:14:48 BST 1999