Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 40 ยท Lists and Recursion

Prolog Built-in List Predicates: length, nth, sort, maplist, foldl

Tour of SWI-Prolog's list library: length, nth0, nth1, last, reverse, sum_list, msort, sort/4, list_to_set, delete, subtract, maplist, include, foldl and findall.

You now know how to write list predicates by hand. In practice you reach for the library first. SWI-Prolog ships library(lists), library(apply), library(aggregate) and library(pairs), all loaded automatically on first use. Knowing what they offer saves hours: most list tasks are one line. This lesson is a guided tour, grouped by purpose.

Prolog is read-only on this site, so the outputs below are what SWI-Prolog prints (shown with the toplevel's usual spacing). The runnable blocks reproduce the main ideas in the Python stand-in, which cannot call library code directly.

Length and positions

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

?- length(L, 2).
L = [_, _].

?- nth0(1, [a, b, c], X).       % zero-based
X = b.

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

?- nth1(I, [a, b, c], b).       % find the index of an element
I = 2.

?- last([1, 2, 3], X).
X = 3.

length/2 is built in and works both ways: with the list given it counts; with the list unbound and the number given it builds a list of fresh variables. length(L, N) with both unbound enumerates [], [_], [_,_], and so on, forever, so be careful.

Reversing, flattening, numbers

PROLOG
?- reverse([1, 2, 3], R).
R = [3, 2, 1].

?- flatten([1, [2, [3, 4]], 5], F).
F = [1, 2, 3, 4, 5].

?- numlist(1, 5, L).
L = [1, 2, 3, 4, 5].

?- sum_list([1, 2, 3], S).
S = 6.

?- max_list([3, 1, 4], M), min_list([3, 1, 4], N).
M = 4,
N = 1.

?- max_member(M, [b, c, a]).     % works on any terms, using standard order
M = c.

Sorting

PROLOG
?- msort([c, a, b, a], L).       % keeps duplicates
L = [a, a, b, c].

?- sort([c, a, b, a], L).        % removes duplicates
L = [a, b, c].

?- sort(0, @>=, [1, 3, 2, 3], L).  % key 0 = whole term, descending, keep duplicates
L = [3, 3, 2, 1].

?- sort(2, @>=, [a-1, b-3, c-2], L).   % sort pairs by their 2nd argument
L = [b-3, c-2, a-1].

?- predsort([Order, A, B]>>compare(Order, A, B), [3, 1, 2], L).
L = [1, 2, 3].

sort/2 sorts by standard order and removes duplicates. sort/4 takes a key (0 for the whole term, or the position of an argument), an order (@< ascending unique, @=< ascending keep duplicates, @> descending unique, @>= descending keep duplicates). predsort/3 lets you supply your own comparison predicate (it drops elements for which the comparison returns =). To sort by a field of a record, put that field first in a pair Key-Value and use keysort/2, which is stable.

Sets and removing elements

PROLOG
?- list_to_set([a, b, a, c, b], S).
S = [a, b, c].

?- delete([a, b, a, c], a, R).
R = [b, c].

?- exclude(==(a), [a, b, a, c], R).
R = [b, c].

?- subtract([1, 2, 3, 4], [2, 4], R).
R = [1, 3].

?- intersection([1, 2, 3], [2, 3, 4], I).
I = [2, 3].

?- union([1, 2], [2, 3], U).
U = [1, 2, 3].

?- sumlist([1, 2], S).      % old name of sum_list; avoid in new code
S = 3.

These treat lists as sets but take no care to keep them sorted. For big sets use library(ordsets) (sorted lists) or association lists (library(assoc)), which are much faster.

Higher-order predicates: maplist, include, foldl

Higher-order predicates take another predicate as an argument. They are the replacement for explicit recursion in most list code. The yall library lets you write an anonymous predicate inline with [X]>>Goal:

PROLOG
?- maplist([X, Y]>>(Y is X * 2), [1, 2, 3], L).
L = [2, 4, 6].

?- maplist(atom, [a, b, c]).          % check a property of every element
true.

?- include([X]>>(X > 1), [1, 2, 3], L).
L = [2, 3].

?- exclude([X]>>(X > 1), [1, 2, 3], L).
L = [1].

?- partition([X]>>(X < 3), [1, 2, 3, 4], In, Out).
In = [1, 2],
Out = [3, 4].

?- foldl([X, A0, A]>>(A is A0 + X), [1, 2, 3], 0, Sum).
Sum = 6.
  • maplist(G, L1), maplist(G, L1, L2), maplist(G, L1, L2, L3): apply G to corresponding elements. It also works backwards if G does.
  • include/exclude/partition: filter by a test.
  • foldl(G, List, V0, V): fold from the left, with G(Element, Acc0, Acc).

You can also pass a plain predicate name: maplist(succ, [1, 2, 3], L) gives L = [2, 3, 4]. Behind the scenes maplist uses call/N, which adds arguments to a goal and runs it.

Collecting all solutions

Backtracking lets you generate solutions; these predicates collect them into a list:

PROLOG
age(ann, 12). age(bob, 34). age(cy, 18).

?- findall(N, age(N, _), Names).
Names = [ann, bob, cy].

?- findall(N-A, (age(N, A), A >= 18), Adults).
Adults = [bob-34, cy-18].

?- setof(A, N^age(N, A), Ages).      % sorted, no duplicates; N^ means "any N"
Ages = [12, 18, 34].

?- bagof(N, age(N, A), L).           % groups by the free variable A
A = 12, L = [ann] ;
A = 18, L = [cy] ;
A = 34, L = [bob].

?- aggregate_all(count, age(_, _), C).
C = 3.

?- aggregate_all(max(A), age(_, A), M).
M = 34.
Predicate Result Fails on no solutions?
findall/3 list, in solution order, duplicates kept no, gives []
bagof/3 one list per binding of free variables yes
setof/3 sorted list without duplicates, per free-variable binding yes
aggregate_all/3 count, sum, max, min, bag, set count and sum give 0; max, min fail

^ tells bagof/3 and setof/3 which variables to ignore when grouping. This is also the answer to the duplicate answers you met in the family tree: setof(U, uncle(U, kim), Us) returns Us = [tom].

Strings and atoms as lists

atom_chars(hello, L) gives L = [h, e, l, l, o]; atom_codes/2 gives character codes; atomic_list_concat([a, b, c], '-', A) gives A = 'a-b-c' and, in split mode, atomic_list_concat(Parts, ',', 'x,y,z') gives Parts = [x, y, z]; split_string("a b c", " ", "", Parts) gives strings. sumlist, last and friends all work on lists, so text processing and list processing meet naturally.

The same ideas in the stand-in

The mini-Prolog stand-in cannot run maplist because it does not implement call/N, but the underlying recursion is exactly what you wrote earlier. The first block spells out what maplist, include and foldl do, with one hand-written predicate per use. The second block emulates how sort/4 behaves in Python so you can try keys and orders.

Python What maplist, include and foldl do (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.

Python Emulating sort/4 (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.

Choosing the right tool

  • Count, sum, extremes: length/2, sum_list/2, max_list/2, or aggregate_all/3.
  • Transform every element: maplist/3. Filter: include/3, exclude/3.
  • Combine into one value: foldl/4 (or aggregate_all/3).
  • Sort: msort/2, sort/2, sort/4, keysort/2, predsort/3.
  • Remove duplicates: sort/2 or list_to_set/2 (which keeps the first occurrences in order).
  • Collect solutions: findall/3, setof/3, aggregate_all/3.

Common mistakes

  • Using delete/3 with an unbound element: it removes everything that unifies. Use exclude/3 with == for exact removal.
  • Using length/2 on a partial list expecting a number, and looping forever.
  • Forgetting that sort/2 removes duplicates while msort/2 does not.
  • Using setof/3 with free variables and getting several groups. Prefix with Var^ or use findall/3 plus sort/2.
  • Assuming findall/3 fails when there are no solutions; it returns [].

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the difference between msort/2 and sort/2?

    Both use standard order. sort/2 drops duplicates; msort/2 keeps them.
  2. 2. What does maplist([X, Y]>>(Y is X * 2), [1, 2, 3], L) give?

    maplist applies the lambda to each pair of corresponding elements.
  3. 3. What does findall(X, member(X, []), L) give?

    findall/3 always succeeds, with an empty list when there are no solutions.
  4. 4. What does the ^ in setof(A, N^age(N, A), Ages) mean?

    Variables not in the template and not marked with ^ are grouped by bagof/setof; N^ avoids that.
  5. 5. How do you sort pairs Key-Value by value descending, keeping duplicates?

    sort/4 takes the argument position of the key and the order @>= (descending, duplicates kept).

Summary

  • Prefer library predicates to hand-written loops: length, nth0/nth1, last, reverse, sum_list, max_list, numlist, flatten.
  • Sort with msort, sort/2, sort/4, keysort and predsort.
  • maplist, include, exclude, partition and foldl with [X]>>Goal replace most recursion.
  • findall, bagof, setof and aggregate_all collect all solutions.
  • Know each predicate's edge cases: duplicates, failure on empty, free variables.

Next: List Patterns: select, permutation and subset