Prolog

lists

---

a list is a sequence of any number of terms

[1, 2, 3]
[a, b, c, d]
[a, [1, 2, 3], tom, 15, date(1, may, 1995)]

a list is actually a pair of a head and a tail

[Head | Tail]
[A, B, C] = [A | [B | [C | []]]] = [A, B | [C]]

---

length/2

length([], 0).
length([_|Tail], N) :-
    length(Tail, N1),
    N is 1 + N1.

?- length([a, b, [c, d], e], N).

?- length(L, 4).

length with CLP(FD)

length([], 0).
length([_|Tail], N) :-
    N #= N1 + 1,
    length(Tail, N1).

---

list predicates

is_list/1 (predefined)

...

?- is_list(17).
?- is_list([1, 2, 3]).

is_list([]).
is_list([X|Xs]) :- is_list(Xs).

member/2 (predefined)

...

?- member(X, [17, 13, 2, 5]).

member(X, [X|Xs]).
member(X, [Y|Ys]) :- member(X, Ys).

prefix/2

...

?- prefix(X, [a, b, c, d]).

prefix([], L).
prefix([X|Xs], [X|Ys]) :- prefix(Xs, Ys).

suffix/2

...

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

suffix(Xs, Xs).
suffix(Xs, [Y|Ys]) :- suffix(Xs, Ys).

del/3

del(X, L, R)

R is L without one of the occurrences of X

...

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

del(X, [X|Xs], Xs).
del(X, [Y|Ys], [Y|Zs]) :- del(X, Ys, Zs).

insert/3

...

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

insert(X, L, R) :- del(X, R, L).

append/3

...

?- append([1, 2], [3, 4, 5], X).

append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

define member/2 using append/3

...

member(X, Xs) :- append(_, [X|_], Xs).

sublist/2

...

sublist(Xs, Ys) :-
    append(As, Bs, Ys),
    append(Xs, Cs, Bs).

prefix(Xs, Ys) :- append(Xs, _, Ys).

suffix(Xs, Ys) :- append(_, Xs, Ys).

sublist(Xs, Ys) :-
    prefix(Ps, Ys),
    suffix(Xs, Ps).

permutation/2

...

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

permutation([], []).
permutation([X|L], P) :-
    permutation(L, L1),
    insert(X, L1, P).