Termination criteria

Terminate when the list is empty

The pattern for this is:

     % 1 terminating condition
     rule([]) :-
          some_processing([]).
     % 2 recursive
     rule([Head|Tail]) :-
          some_processing(Head),
          rule(Tail).

Now, this is only a pattern: the procedures we'll see in this section will all have this pattern as part of them, although there may be additions.

is_list/1

     % 1 terminating condition
     is_list([]) :-
          write('This is a list'),
          nl.
     % 2 recursive
     is_list([_|Tail]) :-
          % we don't have any processing here - which is why we can
          % use an anonymous variable (instead of Head) in the argument
          is_list(Tail).

Try the following goals:

     | ?- is_list([]).
     | ?- is_list([a,b,c]).
     | ?- is_list([X,Y,Z]).

count_elems/2

     % 1 terminating condition
     count_elems([], Total) :-
          Total = 0.                      % processing
     % 2 recursive
     count_elems([Head|Tail], Count) :-
          count_elems(Tail, Sum),         % recursive
          Count is Sum + 1.               % processing

The main difference is that the order of the recursive and processing sub-goals in the recursive rule have been swapped. If we draw a tree to represent the processing of some goal, eg: count_elems([alpha, beta, gamma], Cnt).

the most obvious difference is that it is a reflection of the typical tree shown earlier. This is simply because of the switch of the recursive and processing sub-goals in the second rule.

app/3

     [alpha, beta, gamma]

     [chi, psi, omega]

     [alpha, beta, gamma, chi, psi, omega]

Unfortunately it isn't possible to get this solution simply with the query:

     | ?- List1 = [alpha, beta, gamma], List2 = [chi, psi, omega], [List1|List2] = List3.

(If you don't know what the List3 will be instantiated to, then you should try the query for yourself.)

Instead, we have to write a procedure that will add one list to another, element-by-element. We'll start the process by considering the terminating condition. The assumption implicit in this is that if the first of the original lists is empty, then the result list must be the same as the second original list:

     % 1 terminating condition
     app([], List2, List3) :-
          List2 = List3.

More experienced Prolog programmers always attempt to do as much work as possible in the argument list, rather than writing extra sub-goals. In this example, we can unify List2 and List3 in the argument list simply by calling them the same name. So we can rewrite this rule as a fact:

     % 1 terminating condition
     app([], List, List).

Before looking at the recursive clause, we'll look at the kinds of queries that this will unify with. Here is a sample:

     | ?- app([], [chi, psi, omega], [chi, psi, omega]).

     yes
     | ?- app([], [chi, psi, omega], List3).

     List3 = [chi,psi,omega] ? ;

     no
     | ?- app(Var, [chi, psi, omega], List3).
     
     Var = [] 
     List3 = [chi,psi,omega] ? ;

     no
     | ?- app([], [], Result).

     Result = [] ? ;

     no
     | ?- app(Var, [], Result).

     Var = [] 
     Result = [] ? ;

     no

The first three are predictable. In the case of the third, the first argument of the query is an uninstantiated variable which is unified with [] in the program. The last two are more interesting. It would seem obvious that, if there is a need to write a definition of what is to be done is the first argument is an empty list, then there should be a definition of what is to be done if the second argument is an empty list. (I suppose we ought to also write a definition that would cope when both the first and second arguments are empty lists.) In practice, we don't need to do this as our definition will cover situations where the second list is either empty or not empty.

This brings us to the recursive rule. We have just seen that we can deal with the second argument if it is empty or non-empty. This suggests that the recursive rule should work on the first argument, which we haven't yet dealt with. All we can really say about the first argument is that we want each element of it stuck onto the second argument. We've seen that we can't just "stick" the two lists together, so we are reduced to attaching the first list to the second, one element at a time.

An initial definition that fits into our basic pattern is:

     % 2 recursive
     app([Hd1|Tl1], List2, [Hd3|Tl3]) :-
          Hd1 = Hd3              % this makes the head of the first list
                                 % unify with the head of the third list
          app(Tl1, List2, Tl3).

We can read this as: appending a list is true if it is true that we can unify the head of the first list with the head of the third list and that we can append the tail of the first list, the second list and the tail of the third list.

As with the definition of the terminating condition, we can rewrite this rule more succinctly, simply by renaming the variables used to stand for the head of the first and third lists:

     % 2 recursive
     app([Hd|Tl1], List2, [Hd|Tl3]) :-
          app(Tl1, List2, Tl3).

If we put these two clauses together, we get a procedure that looks like:

     % 1 terminating condition
     app([], List, List).
     % 2 recursive
     app([Hd|Tl1], List2, [Hd|Tl3]) :-
          app(Tl1, List2, Tl3).

Try out a few queries to ensure that this works:

     | ?- app([alpha, beta, gamma], [chi, psi, omega], List3).
     | ?- app([], [chi, psi, omega], List3).
     | ?- app([alpha, beta, gamma], [], List3).
     | ?- app([], [], List3).

Instantiation of variables in app/3