How To Glue Two Lists Together

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 head  a of the first list  [a,b]

		  Solve the subproblem of gluing  [b] to  [c,d,e]

Put the head  a back at the front of the result

But we have a subproblem to solve:

Lop off the head  b of the first list  [b]

		  Solve the subproblem of gluing  [] to  [c,d,e]

Put the head  a back at the front of the result

But 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).