8 - Recursion With Lists

With this example we'll practice the thinking required to develop a recursive definition. We'll also learn more about working with lists.

% Example 08 - Recursion With Lists

% are two lists the same?
same([],[]). 
same([H1|T1],[H2|T2]) :- H1=H2, same(T1,T2).

The example program defines a property same/2 which is only true if two lists, supplied as parameters, are the same. 

Before we can understand the code, we need to learn a little more about lists.

Working With Lists

Let's remind ourselves of prolog lists as a collection of things, for example [a,b,c]. The order of things in a list matters, so [a,b,c] is not the same as [c,b,a]. Repetition matters too, so [a,b,c] is not the same as [a,b,c,c].

If we want to work with the content of a list, we can unify it with variables. For example, [X,Y,Z]=[1,2,3] leaves X=1, Y=2 and Z=3. If we're only interested in the second item, we can use [_X,Y,_Z]=[1,2,3] which only reports Y=2. 

?- [_X,Y,_Z] = [1,2,3].

Y = 2

The underscores tell prolog that we're not interested the result of unifying _X and _Z. We can be even more frugal and just use underscores [_,Y,_]=[1,2,3].

?- [_,Y,_] = [1,2,3].

Y = 2

This only works if we know the length of the lists ahead of writing our code. If a list only has two things in it, then [X,Y,Z]=[1,2] will fail, as will [_,Y,_]=[1,2].

To work with lists of any length, prolog uses a special construct of the form [H|T]. The variable H unifies with the first thing in the list, the head, and the variable T unifies with the rest of the list, the tail. 

Let's look at an example.

?- [H|T] = [1,2,3].

H = 1
T = [2,3]

We can see H takes the value of the first item of the list [1,2,3], and T takes on the value [2,3], the rest of the list. 

Notice that T is a list, and this will always be the case. If the given list has only one item, then T will be the empty list.

?- [H|T] = [1].

H = 1
T = []

Unification with [H|T] only fails if the given list is empty.

?- [H|T] = [].

false

The following table presents the results of [H|T] unifying with an illustrative selection of lists.

[H|T]	H	T
[1,2,3]	1	[2,3]
[1,2,3,4]	1	[2,3,4]
[1,2]	1	[2]
[1]	1	[]
[]	fails
[[1], 2,3]	[1]	[2,3]
[[a,b,c], [d,e],[f,g]]	[a,b,c]	[[d,e],[f,g]]

The last two examples show that if the first item of the given list is itself a list, then H becomes that list.

We're now ready to explore our recursion example.

Are Two Lists The Same?

Let's think about what it means for two lists to be the same. If we explore some examples with a pen and paper, we'll likely make the following observation.

• Two lists are the same if the first items match, the second items match, the third items match, ... and so on until the end of the lists.

Let's see if we can reformulate this in terms of list heads and tails.

• Two lists are the same if their heads are the same, and their tails are the same too.

We're almost there. We can write this as the termination and continuation rules of a recursive definition.

• Termination - Two empty lists are the same.
• Continuation - Two lists are the same if their heads are the same, and their tails are the same.

The continuation rule needs to reduce the problem by one step. It does this by defining the similarity of two lists in terms of the similarity of their tails, which are shortener by one. Repeated application of the continuation rule will eventually lead to empty lists. This is when we need the termination rule to complete our definition.

same/2

The program defines a property same/2 with two rules.

same([],[]). 
same([H1|T1],[H2|T2]) :- H1=H2, same(T1,T2).

The first rule same([],[]) is the termination rule we just defined stating that two empty lists are the same.

The second rule is the continuation rule which says that two lists are the same if their heads are the same, and if their tails are the same. The rule head same([H1|T1],[H2|T2]) looks complicated so let's break it down. We could have written the head as same(L1, L2) where L1 and L2 are the given lists. We would then have to unify L1 with [H1|T1], and L2 with [H2|T2], in the body of the rule as follows.

same([],[]). 
same(L1, L2) :- L1=[H1|T1], L2=[H2|T2],H1=H2, same(T1,T2).

Putting [H1|T1] and [H2|T2] into the head immediately unifies the variables H1, H2, T1 and T2 with the heads and tails of the given lists. Logically the two approaches are the same. This way requires less code and is actually clearer once we get accustomed to how prolog is written.

The remainder of the rule's body asserts that the two heads are the same H1=H2, and that the tails are the same same(T1,T2).

The following five worked examples let us test same/2, and practise our understanding of recursion, unification, and prolog lists.

Example 1 - Equal Lists

Let's check same/2 confirms [1,2,3] and [1,2,3] are the same.

?- same([1,2,3],[1,2,3])

true

Let's talk through how this works.

• same([1,2,3],[1,2,3]) is true if the heads are the same 1=1, and same([2,3],[2,3]) is true.
• same([2,3],[2,3]) is true if the heads are the same 2=2, and same([3],[3]) is true.
• same([3],[3]) is true if the heads are the same 3=3, and same([],[]) is true. 
• same([],[]) is true by the termination rule.

Example 2 - Unequal Lists

Let's check same/2 confirms [1,2,3] and [1,2,4] are not the same.

?- same([1,2,3],[1,2,4])

false

Let's talk through this example.

• same([1,2,3],[1,2,4]) is true if the heads are the same 1=1, and same([2,3],[2,4]) is true.
• same([2,3],[2,4]) is true if the heads are the same 2=2, and same([3],[4]) is true.
• same([3],[4]) is true if the heads are the same 3=4, and same([],[]) is true. This fails because the heads are not the same.

Example 3 - Lists of Different Length

Let's check same/2 correctly handles lists of different length.

?- same([1,2,3],[1,2,3,4])

false

Let's break it down.

• same([1,2,3],[1,2,3,4]) is true if the heads are the same 1=1, and same([2,3],[2,3,4]) is true.
• same([2,3],[2,3,4]) is true if the heads are the same 2=2, and same([3],[3,4]) is true.
• same([3],[3,4]) is true if the heads are the same 3=3, and same([],[4]) is true. 
• same([],[4]) fails because it doesn't unify with any rule's head. It doesn't unify with the continuation rule because the first parameter [] doesn't unify with [H1|T1].

Example 4 - Lists With Variables

The definition for same/2 is good enough for us to use variables in our queries. In this example, we're asking “what values of A and B make [A,2,3] and [1,B,3] the same?”

?- same([A,2,3], [1,B,3]).

A = 1,
B = 2

Let's talk through this example.

• same([A,2,3],[1,B,3]) is true if the heads are the same A=1, and same([2,3],[B,3]) is true. This gives us A=1.
• same([2,3],[B,3]) is true if the heads are the same 2=B, and same([3],[3]) is true. This gives us B=2.
• A=1 and B=3 are only candidate solutions at this stage. If we continue the recursion and find it fails, we then can't say A=1 and B=3 are valid solutions.
• same([3],[3]) is true if the heads are the same 3=3, and same([],[]) is true. 
• same([],[]) is true by the termination rule.

Example 5 - List As Variable

A more interesting query is to ask “which X is the same as [1,2,3]?”

?- same([1,2,3], X).

X = [1,2,3]

The workings of this example are a little more involved, requiring us to track internal variables. Take your time to work through the following. 

• same([1,2,3],X) is true if the heads are the same 1=_H2, and same([2,3],_T2) is true, where _H2 is the head of X, and _T2 is the tail of X.
• same([2,3],_T2) is true if the heads are the same 2=_H3, and same([3],_T3) is true, where _H3 is the head of _T2, and _T3 is the tail of _T2.
• same([3],_T3) is true if the heads are the same 3=_H4, and same([],_T4) is true, where _H4 is the head of _T3, and _T4 is the tail of _T3.
• same([],_T4) is true by the termination rule if []=_T4.

This is enough information for prolog to build X.

• 1=_H2, _H2 is the head of X, and _T2 is the tail of X, so X=[1,_T2].
• 2=_H3, _H3 is the head of _T2, and _T3 is the tail of _T2, so X=[1,2,_T3].
• 3=_H4, _H4 is the head of _T3, and _T4 is the tail of _T3, so X=[1,2,3,_T4].
• []=_T4, so X=[1,2,3].

There is a lot going on here! The first phase is establishing the values of the internal variables and how they are related. The second phase is putting the information together to build X.

Prolog does all this work, normally unseen by us, even for seemingly innocent queries. It isn't necessary to think at this level of detail for most prolog programming, but it is important to have followed a few examples and understood the underlying mechanisms so that we can write better prolog, and more easily find bugs in code that isn't working as we want.

Key Points

• Prolog's built in mechanism for working with the content of arbitrary lists is the construct [H|T] which unifies H with a list's head (the first item), and T with the list's tail (the rest of the list).
• [H|T] fails to unify with an empty list. 
• When [H|T] does unify with a list, T is always a list.
• When [H|T] is used in the head of a rule, the variables H and T are immediately unified with the list supplied as a parameter.
• Prefixing a variable name with an underscore, like _X, tells prolog not to report its value. An underscore _ on its own has the same effect, however multiple uses of _ in a prolog rule don't refer to the same variable.