append/3

Another classical example of recursion is the predicate append/3. This predicate's three arguments are all lists. append(X, Y, Z) is true if the Z is a list that is the result of sticking the list Y onto the end of the list X. For example, append([a,b], [c,d], [a,b,c,d]) is true. The definition of append/3 is similar to that of member/2 in that both involve working down a list item by item. In the case of append/3, however, no test is being carried out, and eventually the end of one of the lists will be reached, leaving the empty list. This gives the base: what is the result of appending an empty list to a list L? Clearly just L. In Prolog:

append([ ], List, List).

What if the first list isn't empty? We need to take its head, save it, and stick it onto the front of the result. The result itself comes about as the consequence of carrying out the same procedures on the tail of the list. This is the recursive clause:

append([Head|Tail], List, [Head|Result]):-
     append(Tail, List, Result).

append/3 can also be used to generate solutions. Here are some examples:

1. last argument a variable

   |?- append([a,b], [c,d], X).
   
   X = [a,b,c,d] ?
   
   yes
   

2. first argument a variable

   |?- append(X, [c,d], [a,b,c,d]).
   
   X = [a,b] ?
   
   yes
   

3. second argument a variable

   |?- append([a,b], X, [a,b,c,d]).
   
   X = [c,d] ?
   
   yes
   

4. first two arguments variables (and multiple solutions requested)

   |?- append(X, Y, [a,b,c,d]).
   
   X = [ ],
   
   Y = [a,b,c,d] ? ;
   
   X = [a],
   
   Y = [b,c,d] ? ;
   
   X = [a,b],
   
   Y = [c,d] ? ;
   
   X = [a,b,c],
   
   Y = [d] ? ;
   
   X = [a,b,c,d],
   
   Y = [ ] ? ;