Структуры и деревья

Наглядным графическим представление структуры является дерево. При таком представлении функтор представляется узлом, а компоненты — ветвями (поддеревьями). Константы и переменные также представляются узлами, но без ветвей. Примеры:

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.