Using Lists

Because a list is really a recursive compound data structure, you need recursive algorithms to process it. The most basic way to process a list is to work through it, doing something to each element until you reach the end.

An algorithm of this kind usually needs two clauses. One of them says what to do with an ordinary list (one that can be divided into a head and a tail). The other says what to do with an empty list.

1. Writing Lists

For example, if you just want to print out the elements of the list, here's what you do:

/* Program ch07e01.pro */

Here are the two write_a_list clauses described in natural language:

    To write an empty list, do nothing.

    Otherwise, to write a list, write its head (which
    is a single element), then write its tail (a list).

The first time through, the goal is:

    write_a_list([1, 2, 3]).

This matches the second clause, with H=1 and T=[2, 3]; this writes 1 and then calls write_a_list recursively with the tail of the list:

    write_a_list([2, 3]).              /* This is write_a_list(T). */

This recursive call matches the second clause, this time with H=2 and T=[3], so it writes 2 and again calls write_a_list recursively:

    write_a_list([3]).

Now, which clause will this goal match? Recall that, even though the list [3] has only one element, it does have a head and tail; the head is 3 and the tail is []. So again the goal matches the second clause, with H=3 and T=[]. Hence, 3 is written and write_a_list is called recursively like this:

    write_a_list([]).

Now you see why this program needs the first clause. The second clause won't match this goal because [] can't be divided into head and tail. So, if the first clause weren't there, the goal would fail. As it is, the first clause matches and the goal succeeds without doing anything further.

Exercise

Is write_a_list tail-recursive? Would it be if the two clauses were written in the opposite order?

2. Counting List Elements

Now consider how you might find out how many elements are in a list. What is the length of a list, anyway? Here's a simple logical definition:

The length of [] is 0.

The length of any other list is 1 plus the length of its tail.

Can you implement this? In Prolog it's very easy. It takes just two clauses:

/* Program ch07e02.pro */

Take a look at the second clause first. Crucially, [_|T] will match any nonempty list, binding T to the tail of the list. The value of the head is unimportant; as long as it exists, it can be counted it as one element.

So the goal:

    length_of([1, 2, 3], L)

will match the second clause, with T=[2, 3]. The next step is to compute the length of T. When this is done (never mind how), TailLength will get the value 2, and the computer can then add 1 to it and bind L to 3.

So how is the middle step executed? That step was to find the length of [2, 3] by satisfying the goal

    length_of([2, 3], TailLength).

In other words, length_of calls itself recursively. This goal matches the second clause, binding

[3] in the goal to T in the clause and

TailLength in the goal to L in the clause.

Recall that TailLength in the goal will not interfere with TailLength in the clause, because each recursive invocation of a clause has its own set of variables. If this is unclear, review the section on recursion in chapter 6.

So now the problem is to find the length of [3], which will be 1, and then add 1 to that to get the length of [2, 3], which will be 2. So far, so good.

Likewise, length_of will call itself recursively again to get the length of [3]. The tail of [3] is [], so T is bound to [], and the problem is to get the length of [], then add 1 to it, giving the length of [3].

This time it's easy. The goal

    length_of([], TailLength)

matches the first clause, binding TailLength to 0. So now the computer can add 1 to that, giving the length of [3], and return to the calling clause. This, in turn, will add 1 again, giving the length of [2, 3], and return to the clause that called it; this original clause will add 1 again, giving the length of [1, 2, 3].

Confused yet? We hope not. In the following brief illustration we'll summarize the calls. We've used subscripts to indicate that similarly-named variables in different clauses--or different invocations of the same clause--are distinct.

length_of([1, 2, 3], L1).

length_of([2, 3], L2).

length_of([3], L3).

length_of([], 0).

L3 =  0+1 = 1.

L2 = L3+1 = 2.

L1 = L2+1 = 3.

Exercises

What happens when you satisfy the following goal?

Write a predicate called sum_of that works exactly like length_of, except that it takes a list of numbers and adds them up. For example, the goal:

What happens if you execute this goal?

3. Tail Recursion Revisited

You probably noticed that length_of is not, and can't be, tail-recursive, because the recursive call is not the last step in its clause. Can you create a tail-recursive list-length predicate? Yes, but it will take some effort.

The problem with length_of is that you can't compute the length of a list until you've already computed the length of the tail. It turns out there's a way around this. You'll need a list-length predicate with three arguments.

One is the list, which the computer will whittle away on each call until it eventually becomes empty, just as before.

Another is a free argument that will ultimately contain the result (the length).

The third is a counter that starts out as 0 and increments on each call.

When the list is finally empty, you'll unify the counter with the (up to then) unbound result.

/* Program ch07e03.pro */

This version of the length_of predicate is more complicated, and in many ways less logical, than the previous one. We've presented it merely to show you that, by devious means, you can often find a tail-recursive algorithm for a problem that seems to demand a different type of recursion.

Exercises

Try both versions of length_of on enormous lists (lists with perhaps 200 to 500 elements). What happens? On long lists, how do they compare in speed?

What happens with the new version of length_of if you give the following goal?

Rewrite sum_of to work like the new version of length_of.

Another Example -- Modifying the List

Sometimes you want to take a list and create another list from it. You do this by working through the list element by element, replacing each element with a computed value.  For example, here is a program that takes a list of numbers and adds 1 to each of them:

/* Program ch07e04.pro */

To paraphrase this in natural language:

    To add 1 to all the elements of the empty list,
        just produce another empty list.

    To add 1 to all the elements of any other list,
        add 1 to the head and make it the head of the result, and then
        add 1 to each element of the tail and make that the tail of the result.

Load the program, and enter the goal add1([1,2,3,4], NewList).

Visual Prolog will return

    NewList=[2,3,4,5]
    1 Solution

Tail Recursion Again

Is add1 tail-recursive? If you're accustomed to using Lisp or Pascal, you might think it isn't, because you think of it as performing the following operations:

Split the list into Head and Tail.

Add 1 to Head, giving Head1.

Recursively add 1 to all the elements of Tail, giving Tail1.

Combine Head1 and Tail1, giving the resulting list.

This isn't tail-recursive, because the recursive call is not the last step.

But--and this is important--that is not how Prolog does it. In Visual Prolog, add1 is tail-recursive, because its steps are really the following:

Bind the head and tail of the original list to Head and Tail.

Bind the head and tail of the result to Head1 and Tail1. (Head1 and Tail1 do not have values yet.)

Add 1 to Head, giving Head1.

Recursively add 1 to all the elements of Tail, giving Tail1.

When this is done, Head1 and Tail1 are already the head and tail of the result; there is no separate operation of combining them. So the recursive call really is the last step.

More on Modifying Lists

Of course you don't actually need to put in a replacement for every element. Here's a program that scans a list of numbers and copies it, leaving out the negative numbers:

/* Program ch07e05.pro */

For example, the goal

    discard_negatives([2, -45, 3, 468], X)

gives X=[2, 3, 468].

And here's a predicate that copies the elements of a list, making each element occur twice:

    doubletalk([], []).

    doubletalk([H|T], [H, H|DoubledTail]) :-
        doubletalk(T, DoubledTail).

4. List Membership

Suppose you have a list with the names John, Leonard, Eric, and Frank and would like to use Visual Prolog to investigate if a given name is in this list. In other words, you must express the relation "membership" between two arguments: a name and a list of names. This corresponds to the predicate

    member(name, namelist).    /* "name" is a member of "namelist" */

In Program 6, the first clause investigates the head of the list. If the head of the list is equal to the name you're searching for, then you can conclude that Name is a member of the list. Since the tail of the list is of no interest, it is indicated by the anonymous variable. Thanks to this first clause, the goal

    member(john, [john, leonard, eric, frank])

is satisfied.

/* Program ch07e06.pro */

If the head of the list is not equal to Name, you need to investigate whether Name can be found in the tail of the list.

In English:

    Name is a member of the list if Name is the first element of the list, or
    Name is a member of the list if Name is a member of the tail.

The second clause of member relates to this relationship. In Visual Prolog:

    member(Name, [_|Tail]) :- member(Name, Tail).

Exercises

Load Program 6 and try the following goal:

    member(susan, [ian, susan, john]).

Add domain and predicate statements so you can use member to investigate if a number is a member of a list of numbers. Try several goals, including

    member(X, [1, 2, 3, 4]).

to test your new program.

Does the order of the two clauses for the member predicate have any significance? Test the behavior of the program when the two rules are swapped. The difference appears if you test the goal

    member(X, [1, 2, 3, 4, 5])

in both situations.

5. Appending One List to Another: Declarative and Procedural Programming

As given, the member predicate of Program 6 works in two ways. Consider its clauses once again:

    member(Name, [Name|_]).
    member(Name, [_|Tail]) :- member(Name, Tail).

You can look at these clauses from two different points of view: declarative and procedural.

From a declarative viewpoint, the clauses say

    Name is a member of a list if the head is equal to Name;
   if not, Name is a member of the list if it is a member of the tail.

From a procedural viewpoint, the two clauses could be interpreted as saying:

    To find a member of a list, find its head;
    otherwise, find a member of its tail.

These two points of view correspond to the goals

    member(2, [1, 2, 3, 4]).

and

    member(X, [1, 2, 3, 4]).

In effect, the first goal asks Visual Prolog to check whether something is true; the second asks Visual Prolog to find all members of the list [1,2,3,4]. Don't be confused by this. The member predicate is the same in both cases, but its behavior may be viewed from different angles.

Recursion from a Procedural Viewpoint

The beauty of Prolog is that, often, when you construct the clauses for a predicate from one point of view, they'll work from the other. To see this duality, in this next example you'll construct a predicate to append one list to another. You'll define the predicate append with three arguments:

    append(List1, List2, List3)

This combines List1 and List2 to form List3. Once again you are using recursion (this time from a procedural point of view).

If List1 is empty, the result of appending List1 and List2 will be the same as List2. In Prolog:

    append([], List2, List2).

If List1 is not empty, you can combine List1 and List2 to form List3 by making the head of List1 the head of List3. (In the following code, the variable H is used as the head of both List1 and List3.) The tail of List3 is L3, which is composed of the rest of List1 (namely, L1) and all of List2. In Prolog:

    append([H|L1], List2, [H|L3]) :-
    append(L1, List2, L3).

The append predicate operates as follows: While List1 is not empty, the recursive rule transfers one element at a time to List3. When List1 is empty, the first clause ensures that List2 hooks onto the back of List3.

Exercise

The predicate append is defined in Program 7. Load the program.

/* Program ch07e07.pro */

Now run it with the following goal:

    append([1, 2, 3], [5, 6], L).

Now try this goal:

    append([1, 2], [3], L), append(L, L, LL).

One Predicate Can Have Different Uses

Looking at append from a declarative point of view, you have defined a relation between three lists. This relation also holds if List1 and List3 are known but List2 isn't. However, it also holds true if only List3 is known. For example, to find which two lists could be appended to form a known list, you could use a goal of the form

    append(L1, L2, [1, 2, 4]).

With this goal, Visual Prolog will find these solutions:

    L1=[], L2=[1,2,4]
    L1=[1], L2=[2,4]
    L1=[1,2], L2=[4]
    L1=[1,2,4], L2=[]
    4 Solutions

You can also use append to find which list you could append to [3,4] to form the list [1,2,3,4]. Try giving the goal

    append(L1, [3,4], [1,2,3,4]).

Visual Prolog finds the solution

    L1=[1,2].

This append predicate has defined a relation between an input set and an output set in such a way that the relation applies both ways. Given that relation, you can ask

    Which output corresponds to this given input?

or

    Which input corresponds to this given output?

The status of the arguments to a given predicate when you call that predicate is referred to as a flow pattern. An argument that is bound or instantiated at the time of the call is an input argument, signified by (i); a free argument is an output argument, signified by (o).

The append predicate has the ability to handle any flow pattern you provide. However, not all predicates have the capability of being called with different flow patterns. When a Prolog clause is able to handle multiple flow patterns, it is known as an invertible clause. When writing your own Visual Prolog clauses, keep in mind that an invertible clause has this extra advantage and that creating invertible clauses adds power to the predicates you write.

Exercise

Amend the clauses defining member in Program 6 and construct the clauses for a predicate even_member that will succeed if you give the goal

    even_member(2, [1, 2, 3, 4, 5, 6]).

The predicate should also display the following result:

    X=2
    X=4
    X=6
    3 Solutions

given the goal

    even_member(X, [1, 2, 3, 4, 5, 6]).