Prolog/Lists

From Wikibooks, the open-content textbooks collection

This section deals with lists in prolog.

[edit] Lists

Any language needs a way to handle collections of objects and prolog is no exception. A list in prolog can look like this:

[a, b, c, d, e]

The brackets are the beginning and the end of the list, and the commas separate the various elements. Here all the elements are constants, but a list can contain all sorts of elements, and different types of element can occur in the same list. The following are examples of valid lists:

[a, A, B, C, D]
[predicate(A,V), predicate(a, V)]
[[a1,a2,a3],[b1,b2,b3],[c1,c2,c3]]
[ [A,B] , [B,C] , predicate([a,b,c],[a,b,d,e,f], _) , c , m , D ]

When using lists in your program, this representation can be difficult to use. You will not always know how long the list that you're dealing with is, or what kind of element you want to retrieve from it. The following notation is usually used when programming with lists:

[Head|Tail]

In this notation the variable Head represents the leftmost element of the list and the variable Tail represents the rest of the list represented as another list. A head can be anything, from a predicate to another list, but the tail is always another list.

The following program shows how to use the head/tail notation.

listsplit([H|T], H, T).

Here, [H|T] is a list, H is the head, and T is the tail. For the query

 ?- listsplit([a,b,c,d,e], a, [b,c,d,e]).

Prolog will answer yes. For the query

 
 ?- listsplit([a,b,c,d,e], A, B).

Prolog will answer:

A = a
B = [b, c, d, e] ;

The program can even be used to 'create' a list:

 ?- listsplit(List, a, [b,c,d,e]).
 List = [a, b, c, d, e] ;

here are some examples of lists, and what heads and tails they result in:

[a,b,c,d,e]

a

[b,c,d,e]

[a]

a

[] (an empty list)

[[a,b,c],a,b,[a,b]]

[a,b,c]

[a,b,[a,b]]

Note that the empty list [ ] cannot be split up and therefore will not unify with [H|T].

Splitting up lists can be done with more than two heads:

[H1, H2, H3|Tail]

This will split a list up into the first three elements, and the rest of the list. Note, however that this will fail if the list has less than three elements.

Now consider the following program:

 last_element([Elem], Elem).
 last_element([_|Tail], Elem) :- last_element(Tail, Elem).

This program finds the last element in a list recursively. Almost all list operations are done in this way, and though it can seem daunting at first it's very important to understand these constructions. This program works as follows:

?- last_element([a,b,c,d,e], Last).
Last = e

First, there is the stop predicate, that says that the last element of a list with one element, is that element. The second line says that the last element (Elem) of a list [_|Tail] is the last element of its tail (Tail). Since we don't care about the head, we use the anonymous variable, _, for it.

[edit] Examples

[edit] The member predicate

Normally , you would use builtin predicate for these list operations, instead of writing them yourself. Builtin predicates are defined by your prolog implementation, but can be used in any program. These implementations are shown here to illustrate how to modify lists.

Member is a standard prolog built-in predicate. You use it like this:

member(Element, List).

Where List is any prolog list, and Element is any element in that list. The following, for instance, return true:

member(a, [a, b, c]).
member(b, [a, b, c]).   
member(c, [a, b, c]).

This query:

 ?- member(Element, [a, b, c]).

Will return the following values for Element:

Element = a;
Element = b;
Element = c;

The member predicate is defined like this:

member(X, [X|_]).        % member(X, [Head|Tail]) is true if X = Head 
                         % that is, if X is the head of the list
member(X, [_|Tail]) :-   % or if X is a member of Tail,
  member(X, Tail).       % ie. if member(X, Tail) is true.

[edit] The append predicate

The built-in predicate append/3 attaches a list to the back of another, in other words, it concatenates two lists. It's used like this:

append(List1, List2, List3)

Where List3 is the concatenation of List1 and List2. The following return true:

append([a, b, c], [1, 2, 3], [a, b, c, 1, 2, 3]).
append([], [a, b, c], [a, b, c]).
append([A, B, C], [1, 2, 3], [A, B, C, 1, 2, 3]).

You can use it to concatenate two lists:

 ?- append([a, b, c], [d, e, f], Result).

 Result = [a, b, c, d, e, f]

Or to divide a list in all possible ways:

 ?- append(List1, List2, [a, b, c]).
 
 List1 = []
 List2 = [a, b, c] ;
 
 List1 = [a]
 List2 = [b, c] ;
 
 List1 = [a, b]
 List2 = [c] ;
 
 List1 = [a, b, c]
 List2 = [] ;
 
 No

You can even use it with three variables. (Try this for yourself to see what the result look like).

The append predicate can be defined like this:

append([], List, List).                    % the stop predicate
append([H|Tail1], List2, [H|Tail3]) :-     % the recursive predicate
         append(Tail1, List2, Tail3) . 

The stop predicate states that the concatenation of an empty list [ ] and a second list, List, is the second list, [ ] + [a,b,c] = [a,b,c]. The recursive predicate will recurse towards this predicate. It states that the concatenated list is [H|Tail3], where H is the first element of the first list and Tail3 is the result of append(Tail1, List2, Tail3) (the tail of the first list appended to the second list). This will take one element off the front of the first list and tag it on the front of the third (the tail of which is not yet certain), until append([], List2, Tail3) is called, which is solved through the stop predicate.

[edit] Reversing a list

Although there are better ways to reverse a list, the simplest method by far is by taking advantage of the append-predicate (see above) and by using recursion.

reverse([], []).              % if there is no list to reverse, the output will also be an empty list
reverse([H|T], R) :- reverse(T, R1), append(R1, [H], R).

Notice that in the second predicate, we make an assumption that T is reversed, and the result placed in R1. Then, we append R1 to [H] (H, encapsulated in a list), and the final result is placed in R.

An example of usage would be

?- reverse([1,2,3,4], R).

R = [4, 3, 2, 1] 

Yes

[edit] Exercises

(1) The built in predicate length() can be used to find the length of a list. For example:

?- length([a,b,95,[1,1,1,1]],X).
X = 4 .
?- length([a,XYZ,59,1,1,1,1],X).
X = 7 .

How might this predicate be defined?

[edit] Answers to Exercises

(1) As you probably guessed, we will use recursion.

length([],0).
length([_|T],L) :- 
   length(T,L1),
   L is L1+1.