Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 40 ยท Lists and Recursion

Prolog Lists: Head, Tail and Recursion on Lists

Learn Prolog lists: the [Head|Tail] pattern, empty list, nested lists and list recursion. Write length, sum, count and maximum predicates one clause per list shape.

Lists are the main data structure in Prolog. A shopping list, a path through a graph, a sequence of tokens in a parser, a queue of tasks: all lists. Because lists are built from terms, unification takes them apart and builds them, and recursion processes them one element at a time. Learn the [Head|Tail] pattern well and most of Prolog opens up.

Prolog is read-only on this site. The Python mini-Prolog stand-in runs the list predicates in this lesson. It writes lists like [a,b,c] with no spaces, whereas SWI-Prolog prints [a, b, c].

What a list is

A list is either:

  • the empty list [], or
  • a non-empty list: a first element (the head) and a list of the remaining elements (the tail).

That two-case definition is recursive, and the rest of this lesson follows from it. Write a list by enumerating its elements:

PROLOG
[red, green, blue]
[1, 2, 3, 4]
[a, 'Hello World', 42, f(x), [nested, list]]
[]

Elements may be any terms, of mixed types, including other lists. Order matters and duplicates are allowed: [a, b] and [b, a] are different lists, and [a, a] has two elements.

The bar notation

The bar | separates the head elements from the tail. [H | T] is a list pattern with head H and tail T:

PROLOG
?- [H | T] = [red, green, blue].
H = red,
T = [green, blue].

?- [First, Second | Rest] = [1, 2, 3, 4, 5].
First = 1,
Second = 2,
Rest = [3, 4, 5].

?- [H | T] = [only].
H = only,
T = [].

?- [H | T] = [].
false.

A few rules to remember:

  • The head is a single element; the tail is always a list. The tail of a one-element list is [].
  • The empty list has no head and no tail, so [H|T] = [] fails.
  • The bar must be followed by exactly one term, normally a variable. [a, b | T] means "a list that starts with a then b".
  • [a, b, c] and [a | [b | [c | []]]] are the same term.

Because it is just unification, you can also build lists by putting a variable on the left: L = [0 | [1, 2]] gives L = [0, 1, 2].

Recursion follows the shape

The definition of a list has two cases, so a predicate over a list normally has two clauses:

PROLOG
% pred(List, ...)
pred([], ...).          % the empty list
pred([H | T], ...) :-   % head and tail
    ...,
    pred(T, ...).       % recurse on the shorter list

The recursion always moves from [H|T] to T, one element shorter, so it ends at []. Compare with Peano numbers: 0 and s(N) are the two shapes of a number, [] and [H|T] are the two shapes of a list.

Length

PROLOG
len([], 0).
len([_ | T], N) :-
    len(T, M),
    N is M + 1.
PROLOG
?- len([a, b, c], N).
N = 3.

The empty list has length 0. A list with a head and tail has length one more than its tail. The head is not used, so we write _. (SWI-Prolog has the built-in length/2, which also works backwards: length(L, 2) gives L = [_A, _B].)

Sum

PROLOG
sum([], 0).
sum([H | T], S) :-
    sum(T, S1),
    S is H + S1.

sum([3, 4, 5], S) gives S = 12.

Count occurrences

PROLOG
count(_, [], 0).
count(X, [X | T], N) :-
    count(X, T, M),
    N is M + 1.
count(X, [Y | T], N) :-
    X \= Y,
    count(X, T, N).

count(a, [a, b, a, c], N) gives N = 2. The X \= Y test in the last clause keeps the clauses exclusive; without it, backtracking would also take the third clause when the head matches, and return wrong extra answers (N = 1, N = 0).

Maximum

PROLOG
maxl([X], X).
maxl([H | T], M) :-
    maxl(T, M1),
    max2(H, M1, M).

max2(A, B, A) :- A >= B.
max2(A, B, B) :- A < B.

The base case here is a one-element list, since the empty list has no maximum. (The library already offers max_list/2 and max_member/2. Our teaching copy is called maxl/2 below so that it does not hide the library version.)

Accessing elements

Without indexes, you take elements off the front:

PROLOG
first([H | _], H).
second([_, H | _], H).

last_elem([X], X).
last_elem([_ | T], X) :- last_elem(T, X).

For positions, the library provides nth0(Index, List, Elem) (zero-based) and nth1/3 (one-based):

PROLOG
?- nth0(1, [a, b, c], X).
X = b.

?- nth1(1, [a, b, c], X).
X = a.

Lists are linked lists: reaching the last element means walking all the others, so repeated indexing is slow. If you need fast random access use other structures (see data structures).

Lists of lists and other shapes

Lists can nest, so a matrix can be a list of rows: [[1,2],[3,4]]. Pairs are often written Key-Value, using the - operator: [a-1, b-2]. Many library predicates (pairs_keys_values/3, sort/4) use that format. Text can be a list of characters: atom_chars(hello, L) gives L = [h, e, l, l, o]; numlist(1, 5, L) gives [1, 2, 3, 4, 5].

Try it: patterns

Python Taking lists apart (mini-Prolog stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice first(L, a): used backwards it builds a list starting with a, with an unbound tail.

Try it: recursion on lists

Python len, sum, count and max (mini-Prolog stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Treating the tail as an element: [H|T] with T = [b] is the list [a, b], not [a, [b]].
  • Forgetting the empty-list clause.
  • Using [H | T1, T2]: after the bar only one term is allowed.
  • Missing the guard in count/3, so extra answers appear on backtracking.
  • Defining a predicate named like a library one (length/2, append/3, max_list/2): in SWI-Prolog, user definitions of library predicates are allowed in most cases, but built-ins such as length/2 cannot be redefined.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What are H and T in [H | T] = [a, b, c]?

    The head is the first element; the tail is the list of the rest.
  2. 2. What is the tail of the list [x]?

    The tail of a one-element list is the empty list.
  3. 3. Which clauses define the length of a list?

    The empty list has length 0; otherwise add one to the length of the tail.
  4. 4. Why does count/3 need X = Y in its last clause?

    Without the guard, matching elements also satisfy the clause for non-matching ones, giving wrong extra answers on backtracking.

Summary

  • A list is [] or [Head | Tail]; the tail is always a list.
  • [a, b, c] is the same term as [a | [b | [c | []]]]; unification takes lists apart and builds them.
  • Recursion over a list has two clauses: the empty list and the head-tail case.
  • Guards keep clauses exclusive so backtracking does not give wrong answers.
  • Lists are linked, so process them front to back.

Next: member, append and Friends