Рекурсивные структуры данных

Дата добавления: 2015-09-15; просмотров: 1869; Нарушение авторских прав

Пролог допускает несколько эквивалентных способов записи списков, соотношение между которыми пояснено таблицей 1. Первая колонка представляет запись списков с помощью функтора «•». Вторая– эквивалентную запись с помощью квадратных скобок. Третья– содержит выражение, являющееся упрощением второй колонки, в котором рекурсивная структура списка оказывается скрытой. В такой записи список представляется в виде последовательности элементов, ограниченной квадратными скобками и разделяемыми запятыми. В качестве элементов в списках приводятся некоторые условные константы a, b, c.

Формальный объект, записанный с использованием функтора «•»	Формальный объект, записанный с использованием квадратных скобок	Запись с помощью элементов
•(a, [ ])	[a│[ ]]	[a]
•(a, •(b, [ ]))	[a│[b│[ ]]]	[a, b]
•(a, •(b, •(c, [ ])))	[a│[b│[c│[ ]]]]	[a, b, c]
•(a, X)	[a│X]	[a│X]
•(a, •(b, X))	[a│[b│X]]	[a, b│X]

Поскольку списки являются более богатой структурой данных, чем обычные константы, с ними связан набор полезных отношений. Фундаментальной операцией является определение вхождения отдельного элемента в список:

Протокол поиска ответа на вопрос

?– member(5, [4, 2, 5, 7]).

member(5, [4, 2, 5, 7]) member(5, [2, 5, 7]) member(5, [5, 7]) Yes Yes Yes

Дополним правило member несколькими фактами:

list([1, 3, 5, 7, 9]).

list([2, 4, 6, 8, 10]).

и продемонстрируем, каким образом можно использовать списки на примере конъюнктивного вопроса:

?– list(X), member(8, X).

X= [2, 4, 6, 8, 10]

Yes

Следующий предикат– сложение списков:

Возможные обращения и варианты ответов:

?– concat_lists([1, 5, 3 ], [2, 4, 7], L).

concat_lists([1, 5, 3], [2, 4, 7], L) concat_lists([5, 3], [2, 4, 7], Z₁) concat_lists([3], [2, 4, 7], Z₂) concat_lists([ ], [2, 4, 7], Z₃) Yes Yes Yes Yes L= [1│Z₁] Z₁= [5│Z₂] Z₂= [3│Z₃] Z₃= [2, 4 ,7] Z₂= [3, 2, 4 ,7] Z₁= [5, 3, 2, 4 ,7] L= [1, 5, 3, 2, 4 ,7]

После выхода из рекурсии будет получен ответ L= [1, 5, 3, 2, 4 ,7].

?– concat_lists([1, 5, 3 ], L, [1, 5, 3, 8, 3]).

concat_lists([1, 5, 3], L, [1, 5, 3, 8, 3]) concat_lists([5, 3], L, [5, 3, 8, 3]) concat_lists([3], L, [3, 8, 3]) concat_lists([ ], L, [8, 3]) Yes Yes Yes Yes L= [8, 3]

Контрольные вопросы

1 Дайте определение списка.

2 Какие способы задания списков вы знаете?

3 Из чего состоит рекурсивное правило?

4 Какая рекурсия называется левосторонней, а какая правосторонней?

<== предыдущая лекция | следующая лекция ==>

Repeat:– repeat. | Управление встроенной базой данных