Lists

11.1 Syntax

[]                       % empty list
[a, b, c]                % three elements
[H|T]                    % head H, tail T
[a, b | T]               % first two elements, then T
[1, [2, 3], f(x), "s"]   % any terms
'[|]'(a, '[|]'(b, []))   % internal representation of [a, b] in SWI-7 (ISO: '.'(a, '.'(b, [])))

?- [H|T] = [1, 2, 3].          % H = 1, T = [2, 3]
?- [A, B|Rest] = [1, 2, 3, 4]. % A = 1, B = 2, Rest = [3, 4]
?- [X] = [1, 2].               % false

11.2 Writing list predicates yourself

% membership
my_member(X, [X|_]).
my_member(X, [_|T]) :- my_member(X, T).

% length
my_length([], 0).
my_length([_|T], N) :- my_length(T, N0), N is N0 + 1.

% append (the most famous Prolog predicate)
my_append([], L, L).
my_append([H|T], L, [H|R]) :- my_append(T, L, R).

% reverse (naive O(n²), and accumulator-based O(n))
naive_reverse([], []).
naive_reverse([H|T], R) :- naive_reverse(T, RT), my_append(RT, [H], R).

my_reverse(L, R) :- rev_acc(L, [], R).
rev_acc([], Acc, Acc).
rev_acc([H|T], Acc, R) :- rev_acc(T, [H|Acc], R).

% last element
my_last([X], X).
my_last([_|T], X) :- my_last(T, X).

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

% nth element (0-based)
nth(0, [X|_], X).
nth(N, [_|T], X) :- N > 0, N1 is N - 1, nth(N1, T, X).

% delete all occurrences
delete_all(_, [], []).
delete_all(X, [X|T], R) :- delete_all(X, T, R).
delete_all(X, [H|T], [H|R]) :- X \= H, delete_all(X, T, R).

% flatten
my_flatten([], []) :- !.
my_flatten([H|T], F) :- !, my_flatten(H, FH), my_flatten(T, FT), append(FH, FT, F).
my_flatten(X, [X]).

11.3 The power of relations: append in many directions

?- append([1, 2], [3], L).           % L = [1, 2, 3]      concatenate
?- append(X, [3], [1, 2, 3]).        % X = [1, 2]         remove suffix
?- append(X, Y, [1, 2]).             % all splits: X=[],Y=[1,2]; X=[1],Y=[2]; X=[1,2],Y=[]
?- append(_, [Last], [a, b, c]).     % Last = c
?- append(_, [X, Y|_], [1, 2, 3]).   % adjacent pairs
?- append(Prefix, _, [a, b, c]).     % all prefixes

11.4 Built-in list predicates (library(lists), autoloaded)

member(X, L)          memberchk(X, L)        % memberchk: deterministic
append(L1, L2, L3)    append(ListOfLists, L)
length(L, N)          % also generates lists: length(L, 2) → L = [_, _]
reverse(L, R)         nth0(I, L, E)          nth1(I, L, E)
last(L, X)            msort(L, S)            sort(L, S)            % sort/2 removes duplicates
sort(Key, Order, L, S)                        % e.g. sort(0, @>=, L, S) keeps dups, descending
predsort(Pred, L, S)  permutation(L, P)      select(X, L, Rest)    selectchk(X, L, R)
subtract(L1, L2, R)   intersection(A, B, I)  union(A, B, U)        delete(L, X, R)
exclude/include/partition (library(apply))   list_to_set(L, S)     sum_list(L, S)
max_list(L, M)        min_list(L, M)         max_member(M, L)      numlist(1, 5, L)
nextto(X, Y, L)       sumlist/3              last/2                 flatten(L, F)
pairs_keys_values(Pairs, Ks, Vs)              exclude(Pred, L, R)   same_length(A, B)

?- length(L, N).        % enumerates lists of increasing length
?- select(b, [a, b, c], R).   % R = [a, c]
?- select(X, [a, b, c], R).   % pick each element in turn
?- permutation([1, 2, 3], P).
?- sort(0, @>=, [3, 1, 3, 2], L).   % L = [3, 3, 2, 1]

🧪 Part I Exercises

Extend family.pl with uncle/2, aunt/2, cousin/2, descendant/2.

Write count(X, List, N) counting occurrences.

Write my_max(List, Max) and my_min(List, Min).

Implement palindrome(L) using reverse/2.

Write range(Low, High, List) producing [Low..High].

Implement compress/2 removing consecutive duplicates ([a,a,b,c,c] → [a,b,c]).

Write insert_sorted(X, Sorted, Result) and use it to implement insertion sort.

Write hanoi(N, From, To, Via) printing the moves for the Towers of Hanoi.

Define a graph with cycles and write path/3 returning the visited path without looping.

Implement Peano multiplication times(X, Y, Z) and test it in multiple directions.