Наглядным графическим представление структуры является дерево. При таком представлении функтор представляется узлом, а компоненты — ветвями (поддеревьями). Константы и переменные также представляются узлами, но без ветвей. Примеры:
parents(charles, elizabeth, philip).
a + b * c % +(a,*(b,c))
book(moby_dick, author(herman, melville))
| 
| 
|
Пример представления синтаксической структуры простого предложения.
sentence(noun(X), verb_phrase(verb(Y), noun(Z)))
sentence(noun(john), verb_phrase(verb(likes), noun(mary)))
Пример с множественным включением переменной:
f(X, g(X, a))
| 
| 
|
Списки
Список — это упорядоченная последовательность элементов. Элементом списка может быть любой терм, в том числе и другой список. Количество элементов, входящих в список, называется длиной списка. Возможен список, не содержащий ни одного элемента, называемый пустым списком.
Считают, что всякий непустой список состоит из головы (head) и хвоста (tail). Головой списка называют первый элемент, а хвостом — список, состоящий из всех элементов данного списка, кроме первого элемента. Например: в списке a, b, c голова — это элемент a, а хвост — это список b, c. В списке, состоящем из одного элемента, хвост является пустым списком.
В Прологе список списки представляются так:
· пустой список представляется константой [] (пустые квадратные скобки).
· непустой список представляется бинарной структурой, функтор которой — точка, а первый и второй компоненты — голова и хвост списка соответственно (т. е. первый компонент может быть любым термом, а вот второй — только константой [] либо структурой с функтором точка).
Примеры:
[]
'.'(1,'.'(2,[]))
'.'(mary,'.'(ann,'.'(alice,'.'(jane,[]))))
'.'(a,'.'(data(b,c,d),[]))
'.'(f('.'(b,[])),[])
| 
| 
| 
|
Для записи списков удобно использовать списковую нотацию. При использовании этой нотации элементы списка записывают в квадратных скобках через запятую. Можно указывать не все элементы списка, а только один или несколько начальных элементов; остальные задаются в виде списка после вертикальной черты. Примеры:
[1, 2] % '.'(1,'.'(2,[]))
[mary, ann, alice, jane] % '.'(mary,'.'(ann,'.'(alice,'.'(jane,[]))))
[a, b | []] % [a,b]
[a | [b, c, d]] % [a,b,c,d]
[a, b | [c, d]] % [a,b,c,d]
[a, b, c | [d]] % [a,b,c,d]
Примеры вложенных списков:
[a,[b,c]]
[[a]]
[[],[a]]
[[a,b],c,[d,[e,f]]]
| 
| 
|
Разумеется, в списках можно использовать переменные. При этом использование переменной в качестве хвоста списка позволяет задать список переменной длины. Примеры:
?- [mary, ann] = [X, Y]. % X = mary, Y = ann.
?- [mary, ann, jane] = [X, Y]. % false.
?- [mary, ann, jane] = [X, Y | Z]. % X = mary, Y = ann, Z = [jane].
?- [mary, ann] = [X, Y | Z]. % X = mary, Y = ann, Z = [].
?- [mary, ann, jane, alice] = [X, Y | Z]. % X = mary, Y = ann, Z = [jane, alice].
?- [mary, ann, jane] = [_, X | _]. % X = ann.
?- [mary, ann] = [_, X | _]. % X = ann.
?- [mary] = [_, X | _]. % false.
?- [alice, ann] = [_, _]. % true.
?- [alice] = [_, _]. % false.
?- [alice, ann, jane] = [_, _]. % false.
?- [alice, ann, jane] = [_, _ | _]. % true.
?- [alice, ann, jane] = [_, _ | X]. % X = [jane].
?- [ann, ann, jane] = [X, X | _]. % X = ann.
?- [ann, jane, ann] = [X, X | _]. % false.
?- [a, b, c, d, e] = [X, Y | Z], U = [Y, X | Z]. % X = a, Y = b, Z = [c, d, e], U = [b, a, c, d, e].
?- [[a, b], [c, d]] = [[X | _], [Y | _]], Z = [X, Y]. % X = a, Y = c, Z = [a, c].
?- [f([a, b])] = [f([X | _]) | _]. % X = a.
Обработка списков произвольной длины осуществляется с использованием рекурсивно определенных предикатов. Пример определения принадлежности элемента списку (поиска элемента в списке).
list_member(X, [X | _]).
list_member(X, [_ | T]):- list_member(X, T).
Использование:
?- list_member(ann, [ann, mary, jane]). % true; false.
?- list_member(mary, [ann, mary, jane]). % true; false.
?- list_member(alice, [ann, mary, jane]). % false.
?- list_member(ann, [ann, mary, ann, jane]). % true; true; false.
?- list_member(X, [ann, mary, jane]). % X = ann; X = mary; X = jane; false.
?- list_member(mary, [ann, Y, jane]). % Y = mary; false.
?- list_member(ann, [X, Y]), list_member(mary, [X, Y]). % X = ann, Y = mary; X = mary, Y = ann; false.
?- L = [_, _], list_member(ann, L), list_member(mary, L). % L = [ann, mary]; L = [mary, ann]; false.
?- L = [_, _], list_member(ann, L). % L = [ann, _G7754]; L = [_G7751, ann]; false.
?- list_member(ann, L). % L = [ann|_G7749]; L = [_G7748, ann|_G7752]; L = [_G7748, _G7751, ann|_G7755]; …
?- list_member(X, [4, 2, 5, 1, 3]), X < 3. % X = 2; X = 1; false.
?- list_member([X | _], [a, [b, c], [], [d]]). % X = b; X = d; false.
Поиск соседних элементов:
list_nextto(X, Y, [X, Y | _]).
list_nextto(X, Y, [_ | T]):- list_nextto(X, Y, T).
Использование:
?- list_nextto(2, 3, [1, 2, 3, 4, 5]). % true; false.
?- list_nextto(2, 1, [1, 2, 3, 4, 5]). % false.
?- list_nextto(2, 4, [1, 2, 3, 4, 5]). % false.
?- list_nextto(2, X, [1, 2, 3, 4, 5]). X = 3; false.
?- list_nextto(X, 3, [1, 2, 3, 4, 5]). % X = 2; false.
?- list_nextto(X, 3, [1, 2, 3, 4, 5, 3, 3]). % X = 2; X = 5; X = 3; false.
?- list_nextto(X, Y, [1, 2, 3, 4]). % X = 1, Y = 2; X = 2, Y = 3; X = 3, Y = 4; false.
?- X = [_, _, _, _], list_nextto(a, b, X), list_nextto(c, d, X). % X = [a, b, c, d]; X = [c, d, a, b]; false.
Возведение каждого элемента в квадрат:
square([], []).
square([X | T], [Y | S]):- Y is X ** 2, square(T, S).
Использование:
?- square([2, 3, 4], L). % L = [4, 9, 16].
?- square([1 + 2, 3 + 4], L). % L = [9, 49].
Сумма элементов:
sum([], 0).
sum([X | T], Y):- sum(T, Z), Y is Z + X.
Использование:
?- sum([1, 2, 3, 4], X). % X = 10.
Список биграмм:
bigram([], []).
bigram([_], []).
bigram([X, Y | T], [t(X, Y) | S]):- bigram([Y | T], S).
Использование:
?- bigram([1, 2, 3, 4], L). % L = [t(1, 2), t(2, 3), t(3, 4)]; false.
?- bigram(L, [t(1, 2), t(2, 3)]). % L = [1, 2, 3]; false.
?- bigram(L, [t(1, 2), t(3, 2)]). % false.
«Молния»
zip([], [], []).
zip([X1 | T1], [X2 | T2], [t(X1, X2) | T]):- zip(T1, T2, T).
Использование:
?- zip([1, 2, 3], [a, b, c], L). % L = [t(1, a), t(2, b), t(3, c)].
?- zip(L1, L2, [t(a, 1), t(b, 2)]). % L1 = [a, b], L2 = [1, 2]; false.
?- zip([1, 2, 3], [a, b], L). % false.
Сцепление списков
list_append([], L, L).
list_append([X | T], L, [X | S]):- list_append(T, L, S).
Использование:
?- list_append([a, b], [c, d, e], L). % L = [a, b, c, d, e].
?- list_append(X, Y, [a, b, c]). % X = [], Y = [a, b, c]; X = [a], Y = [b, c]; X = [a, b], Y = [c]; X = [a, b, c], Y = []; false.
?- list_append([a, b], [c], L), list_append(L, [d, e], M). % L = [a, b, c], M = [a, b, c, d, e].
Разумеется, рекурсия может использоваться не только со списками. Рассмотрим следующие примеры:
Факториал (произведение всех целых чисел, начиная с 1 и до данного числа).
factorial(0, 1).
factorial(N, X):- N > 0, M is N - 1, factorial(M, Y), X is Y * N.
Использование:
?- factorial(5, N). % N = 120; false.
?- factorial(25, N). % N = 15511210043330985984000000; false.
Числа Фибоначчи (каждое следующее равно сумме двух предыдущих).
Наивная (неправильная) реализация
fibonacci(1, 1).
fibonacci(2, 1).
fibonacci(N, X):- N > 2,
N1 is N - 1, fibonacci(N1, X1),
N2 is N - 2, fibonacci(N2, X2),
X is X1 + X2.
Правильная реализация
fibonacci(1, 1, 1).
fibonacci(N, X1, X2):- N > 1,
N1 is N - 1, fibonacci(N1, X0, X1),
X2 is X0 + X1.
Использование:
?- fibonacci(5, N, M). % N = 5, M = 8; false.
?- fibonacci(100, N, M). % N = 354224848179261915075, M = 573147844013817084101; false.
