Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 40 ยท Lists and Recursion

Prolog member/2, append/3, select/3 and Other List Relations

Master Prolog's core list predicates: how member/2 and append/3 are defined, how append works in every direction, and how to build prefix, suffix, sublist and select from them.

A handful of list predicates appear in almost every Prolog program: member/2, append/3, select/3, prefix, suffix and sublist. They are all defined by a few lines of recursion, and, because they are relations rather than functions, each one works in several directions. Writing them yourself is the best exercise for understanding Prolog lists.

Prolog is read-only on this site. The Python mini-Prolog stand-in runs the definitions exactly as shown. SWI-Prolog already provides member/2, append/3 and select/3 in library(lists); here we write our own to see how they work.

member/2

member(X, List) is true if X is an element of List:

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

Read it: X is a member of a list if it is the head, or if it is a member of the tail. Two clauses, the first is the "found it" case, the second skips one element and tries again.

PROLOG
?- member(b, [a, b, c]).
true.

?- member(z, [a, b, c]).
false.

?- member(X, [a, b, c]).
X = a ;
X = b ;
X = c.

With an unbound first argument, member/2 generates: it is a way to choose an element of a list, and backtracking visits each. This is the standard idiom for "try each candidate" in generate-and-test programs: member(X, [1,2,3,4]), X * X > 5. When you only need a yes/no and not extra solutions, memberchk(X, List) succeeds at most once, leaving no choice point.

Notice that member(a, [a, b, a]) succeeds twice: once for each occurrence. Add once/1 or memberchk/2 if that matters.

append/3

append(L1, L2, L3) is true if L3 is the list L2 placed after L1:

PROLOG
append([], L, L).
append([H | T], L, [H | R]) :- append(T, L, R).

The base case: appending L to the empty list gives L. The recursive case: the result of appending to [H|T] starts with H followed by the result of appending to T. The recursion walks the first list; its cost is proportional to the length of L1.

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

One definition, many uses

Because append/3 is a relation, you can leave any argument unbound:

PROLOG
?- append(X, [3], [1, 2, 3]).        % what do I add 3 to, to get [1,2,3]?
X = [1, 2].

?- append([1, 2], Y, [1, 2, 3, 4]).  % what comes after?
Y = [3, 4].

?- append(X, Y, [1, 2]).             % all ways to split
X = [], Y = [1, 2] ;
X = [1], Y = [2] ;
X = [1, 2], Y = [].

The third query splits a list in every possible way: backtracking turns append/3 into a generator of pairs. This is the pattern behind most of the predicates below.

flowchart LR
    A["append(X, Y, [1,2])"] --> B["X = [] , Y = [1,2]"]
    A --> C["X = [1] , Y = [2]"]
    A --> D["X = [1,2] , Y = []"]

One query, three ways to cut the list.

Building more predicates from append

PROLOG
prefix(P, L)   :- append(P, _, L).
suffix(S, L)   :- append(_, S, L).
sublist(Sub, L) :- append(_, T, L), append(Sub, _, T).

last_of(L, X)  :- append(_, [X], L).
adjacent(X, Y, L) :- append(_, [X, Y | _], L).
  • prefix/2: P is the front part of L.
  • suffix/2: S is the tail part of L.
  • sublist/2 (a contiguous piece): skip some front elements (any _), then take a prefix of what remains.
  • last_of/2: the list is anything followed by one last element.
  • adjacent/3: X and Y appear next to each other.
PROLOG
?- prefix(P, [a, b]).
P = [] ;
P = [a] ;
P = [a, b].

?- adjacent(X, Y, [1, 2, 3]).
X = 1, Y = 2 ;
X = 2, Y = 3.

Notice how declarative these are: no loops or indexes, only a statement of what the answer looks like, with append/3 doing the search. (In sublist/2, the empty list is a sublist at every position, so [] appears repeatedly; filter it out with Sub \= [] if you do not want it.)

select/3

select(X, List, Rest) removes one occurrence of X from List, leaving Rest:

PROLOG
select(X, [X | T], T).
select(X, [H | T], [H | R]) :- select(X, T, R).
PROLOG
?- select(b, [a, b, c], R).
R = [a, c].

?- select(X, [a, b, c], R).
X = a, R = [b, c] ;
X = b, R = [a, c] ;
X = c, R = [a, b].

Used with an unbound X it picks an element and gives the rest. Used the other way round it inserts: select(x, L, [a, b]) places x at every possible position, giving L = [x, a, b], L = [a, x, b], L = [a, b, x]. That is the heart of permutations, which you will write in a later lesson.

Try it: member and append in all directions

Python member and append (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.

The query member(a, [a, b, a]) shows two true answers (printed as true ; then true.), one for each position of a.

Try it: select, in and out

Python select/3 removes and inserts (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.

Efficiency notes

  • member/2 and memberchk/2 walk the list: O(n).
  • append(L1, L2, L3) with L1 bound costs O(length of L1). Building a long list by repeatedly appending at the end is quadratic; see accumulators and difference lists.
  • With both L1 and L2 unbound and L3 unbound, append enumerates infinitely many lists. Make sure at least the first or the third argument is bound.
  • Splitting with append(X, Y, L) produces length(L) + 1 answers.

Common mistakes

  • Using append/3 to add a single element: append(L, [X], R) works, but [X | L] adds at the front in constant time.
  • Forgetting that member/2 returns once per occurrence.
  • Calling append(X, Y, Z) with all unbound and expecting a finite answer.
  • Redefining these names in your file while also loading the library: define your own under another name if you need a variant.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many answers does member(a, [a, b, a]) give?

    member/2 succeeds once for every occurrence, so there are two.
  2. 2. What does append(X, Y, [1, 2]) produce?

    append/3 is a relation, so with only the result bound it enumerates all splits: three answers.
  3. 3. How is prefix(P, L) defined with append/3?

    A prefix is a front part: P followed by anything gives L.
  4. 4. What does select(x, L, [a, b]) do?

    Used backwards, select/3 inserts the element at each possible place.

Summary

  • member/2 is a two-clause recursion that also generates elements on backtracking; memberchk/2 gives only the first.
  • append/3 concatenates, splits, finds prefixes and suffixes, all from one definition.
  • prefix, suffix, sublist, last_of and adjacent are one-liners built on append/3.
  • select/3 removes an element, or inserts one when run backwards.
  • Make sure the arguments you rely on are bound, or the search may be endless.

Next: Accumulators and Reverse