Prolog/Lists

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 atoms, 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]
[p(A,V), p(a, V)]
[[a1,a2,a3],[b1,b2,b3],[c1,c2,c3]]
[[A,B], [B,C], quu([a,b,c],[a,b,d,e,f],_), c, m, D]

Most prolog code will not define a list explicitly, like these examples, but rather handle lists of any length, with many possible elements. To handle lists without knowing what's inside them or how long they are, you use the bar notation:

[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.

Some default library rules are provided, e.g., length, reverse, append (also, these can be defined easily, as shown at the bottom of this page). To see how these work, try the following codes:

 ?- length([1, 3, 6], What).

Prolog will answer 3.

 ?- append([a], b, Z).

 ?- append([a], [b], Z).

Observe the difference here.

 ?- append(X, [1, 2], [1, 1, 2]).

 ?- reverse([1,2], What).

The following program shows how to use this.

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:

List	Head	Tail
[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 fewer than three elements.

Now consider the following program:

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

This relation defines the last element of a list. It can be used as a program to find a list's last element:

?- last([a,b,c,d,e],X).
X = 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.

Examples

The member predicate

Normally, you would use built in predicates for these list operations, instead of writing them yourself. Built in 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, succeeds (returns 'Yes'):

 ?- 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.

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(Xs, Ys, Zs)

Where Zs is Ys appended to Xs. The following succeed:

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 append two lists:

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

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

Or to split a list into left and right parts,

 ?- append(ListLeft, ListRight, [a, b, c]).
 
 ListLeft  = []
 ListRight = [a, b, c] ;
 
 ListLeft  = [a]
 ListRight = [b, c] ;
 
 ListLeft  = [a, b]
 ListRight = [c] ;
 
 ListLeft  = [a, b, c]
 ListRight = [] ;
 
 No

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

The append predicate can be defined like this:

append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

The first line simply unifies the last two lists, it succeeds for queries like: append([], [a,b,c], [a,b,c]). or append([], X, [e]). in which case it would bind X = [e]. The second line (the recursive clause) declares that, given append(A,B,C) the head of A is equal to the head of C, and appending the tail of A, with B, gives the tail of C.

Due to the nondeterminism of Prolog, append/3 has many uses. It can be used as another way to implement last/2 which was defined earlier.

last(List, Last) :- append(_, [Last], List).

Many more definitions are possible,

split(List, Pivot, Left, Right) :- append(Left, [Pivot|Right], List).

?- split([o,o,x,e,e,e], x, L, R).
L = [o, o],
R = [e, e, e] ;

?- split(A, -, [o,o], [u,u,u]).
A = [o, o, -, u, u, u].

Reversing a list

We will look at two ways to reverse a list, first of all the naive way is to simply keep taking the head off and appending it onto the end,

reverse([],[]).
reverse([X|Xs],YsX) :- reverse(Xs,Ys), append(Ys,[X],YsX).

Executing it means that you traverse the list over and over again appending each time, A more efficient version can be created by taking the definition of append:

append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

and changing it slightly,

revappend([], Ys, Ys).
revappend([X|Xs], Ys, Zs) :- revappend(Xs, [X|Ys], Zs).

then,

reverse(Xs,Ys) :- revappend(Xs,[],Ys).

The strategy used in revappend is called an accumulating parameter.

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?

Answers to Exercises

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

len([], 0).
len([_ | Tail], Length) :-
    len(Tail, Length1),
    Length is Length1 + 1,!.

Another solution which uses tail recursion optimisation and Prolog's arithmetic (And therefore uses less stack space):

% 0 - Calling Rule
cl(List, Out) :-
	call(List, 0 , Out).

% 1 - Terminating condition
call([], Count, Count).

% 2 - Recursive rule
call([H|T], Count, Out) :-
	Count1 is Count + 1,
	call(T, Count1, Out).

---

prev:Variables next:Math, Functions and Equality