Lists in Prolog¶

"We like lists because we don't want to die." - Umberto Eco

Prolog has a number of useful built-in relations for working with lists. These include:

Relation	Description
`append(X, Y, Z)`	True if appending lists X and Y yields Z
`reverse(X, Y)`	True if list X is the reverse of list Y
`permutation(X, Y)`	True if list X is a permutation of list Y
`sort(X, Y)`	True if list Y is the sort of list X
`length(L, N)`	True if list L has integer length N
`member(X, Y)`	True if X is an element of list Y

Example

Here are some examples of queries involving lists:

?- length([a,b,c,d], 4).` Succeeds. 2. ?- length([a,b,c], 4).

Fails.

3.

?- length([a,b,c], N).

Succeeds with N = 3

```
?- length(L, 0).
```

Succeeds with L = []

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

Succeeds.

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

Fails.

```
?- member(X, [a,b,c,d]).
```

Can succeed in four ways, namely X = a or X = b or X = c or X = d.

```
?- append([a], [b,c,d], L).
```

Succeeds with L = [a,b,c,d]

```
?- append(X, Y, [a,b,c,d]).
```

Can succeed in five ways, namely X = [], Y = [a,b,c,d], or X = [a], Y = [b,c,d], or ...

Manipulating Lists¶

Prolog lists are inherently linked list (as in functional languages like Racket or Haskell). A list is either empty ([]) or has a head (first element) and a tail (the list of remaining elements). Another name for the head and the tail are the first (element) and the rest (of the list).

In Prolog, we can either write lists:

by specifying all the elements individually, e.g., writing [A] or [A,B] or [A,B,C]
by specifying the head element and the tail (a list of the remaining elements), writing [H|T]
a combination of the two, specifying the first few elements, and then a tail (a list of the remaining elements), e.g., writing [A,B|T] or [A,B,C|T]

Note that a list of the form [H|T] is always non-empty because it contains the element H. The tail T should be a list (empty or non-empty), not a single value.

Example

The following equalities hold:

[1,2,3]       ==  [ 1 | [2,3] ].
[1,2,3]       ==  [ 1, 2 | [3] ].
[red, green]  ==  [ red | [green] ].
[milk]        ==  [ milk | [] ].

Defining Recursive Predicates on Lists¶

As in functional languages like Racket, we can define predicates on lists by recursion. We just need to be careful to remember that we are defining logical relations (that succeed or fail), not mathematical functions (that return values).

Example

The length predicate is already built into Prolog, but here's how we could have defined it ourself:

% Base case: the empty list has length 0
length([], 0).

% Recursive case: for nonempty lists, the length is one more than the length of the tail.
length([_|T], N) :- length(T,TailLength), N is TailLength+1.

Example

The member predicate is already built into Prolog, but here's how we could have defined it ourself:

% Base case: E is a member of any list starting with E.
member(E, [E|_]).

% Recursive case: E is a member of a list if it's a member of the tail.
member(E, [_|T]) :- member(E, T)

Importantly, note that we don't write a (base) case for searching for E in the empty list! An element E is never a member of [], and we don't need (or want) to write a rule that explicitly fails in such a case. Rather, we write rules for the cases that should succeed, and Prolog will automatically fail in all other cases.

Example

The append predicate is already built into Prolog, but here's how we could have defined it ourself:

% Base case: appending [] to a list yields that list.
append([], M, M).

% Recursive case: if T appended to M yields TM, then [H|T] appended to M yields [H|TM].
append([H|T], M, [F|TM]) :- append(T,M,TM).

This function is a little harder to follow, but we can think about it by example:

append([1,2], [3,4], [1,2,3,4]) succeeds (by the second rule) because [1,2] == [1|[2]] and [1,2,3,4] == [1|[2,3,4]] and
append([2], [3,4], [2,3,4]) succeeds (by the second rule) because [2] == [2|[]] and [2,3,4] == [2|[3,4]] and
append([], [3,4], [3,4]) succeeds (by the first rule)

Previous: 4.6 Prolog to English

Next: 4.8 Arithmetic in Prolog