Manipulating Lists

“I don’t like the sound of all the lists he’s making”
—Ben Stein

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)