“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: > >1.
> > ?- length([a,b,c,d], 4).` > > >
Succeeds. > >2. >
> ?- length([a,b,c], 4). > > > Fails. >
>3. > > ?- length([a,b,c], N). > > >
Succeeds with N = 3 > >4. >
> ?- length(L, 0). > > > Succeeds with
L = [] > >5. >
> ?- member(c, [a,b,c,d]). > > > Succeeds.
> >6. > > ?- member(e, [a,b,c,d]). > >
> Fails. > >7. >
> ?- member(X, [a,b,c,d]). > > > Can succeed
in four ways, namely X = a or X = b or
X = c or X = d. > >8. >
> ?- append([a], [b,c,d], L). > > > Succeeds
with L = [a,b,c,d] > >9. >
> ?- 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 …
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:
[A] or [A,B] or [A,B,C][H|T][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: >
>prolog > [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: >
>prolog >% 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: >
>prolog >% 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: >
>prolog >% 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