Lists in Prolog - Thinking as Computation - page 144

∗ Example 4: Joining two lists

Here is a more advanced example. Define a predicate join that concatenates two lists:
?- join([a,b,c,d],[e,f,g],L).
L=[a,b,c,d,e,f,g]
Yes
?- join([],[a,b,c,d],L).
L=[a,b,c,d]
Yes

Prolog systems provide a predefined predicate, append , with exactly this behavior,
but again a version is defined here as a recursive predicate.
The predicate join needs to determine what the third argument (the answer)
should be for any two lists. The first list can be empty or nonempty, and the sec-
ond list can also be empty or nonempty. However, it turns out that it is sufficient to
do recursion on the first argument only:

1. Write clauses to handle the case where the first argument is [] and the second

argument is any list L ;

2. Write clauses to handle the case where the first argument is [H|T] and the sec-

ond argument is any list L (assuming that join already works when the first
argument is T and the second argument is L ).

This leads to the following two clauses:
% Joining [] and any list L produces L itself.
join([],L,L).
% If joining T and L produces the list Z,
% then joining [H|T] and L produces the list [H|Z].
join([H|T],L,[H|Z]) :- join(T,L,Z).

The head of the second clause is quite complex. Much of the work of join is done by
unification with this head.
A trace is shown in figure 7.2. As the query succeeds at each level, new elements
are added to the third argument, building the final concatenated list. Here is how the
unification works:

1. The top-level query is join([a,b,c,d],[e,f],R) .

2. This does not unify with join([],L,L) , but it unifies with join([H|T],L,[H|Z])

for the following values: H=a , T=[b,c,d] , L=[e,f] , and R=[a|Z] .