5. Ветвление-выбор

6. Стандартные математические предикаты

.

.

7. СПИСКИ И ОПЕРАЦИИ НАД НИМИ (list = integer*)

Рекурсивное определение списка.

Список — это структура данных, определяемая следующим образом:

1. пустой список ([ ]) является списком;

2. структура вида [H|T] является списком, если H — первый элемент списка (или несколько первых элементов списка, перечисленных через запятую), а T — список, состоящий из оставшихся элементов исходного списка.

В императивных языках основной структурой данных являются массивы. В Прологе так же, как и в Лиспе, основным составным типом данных является список.

[] — пустой список, т.е. список, не содержащий элементов (в Лисп - nil).

Элементы списка могут быть любыми, в том числе и списками.

В классическом Прологе элементы списка могут принадлежать разным доменам, В Турбо Прологе, в связи со строгой типизацией, все элементы списка должны принадлежать одному домену. Однако можно разместить в одном списке объекты разной природы, используя домен с соответствующими альтернативами.

Операция "|" позволяет разделить список на хвост и голову (в Лиспе - car и cdr) или приписать объект (объекты) к началу списка (cons в Лиспе). Данное определение позволяет организовывать рекурсивную обработку списков, разделяя непустой список на голову и хвост.

Чтобы организовать обработку списка достаточно задать базис рекурсии (правило или факт, определяющее, что нужно делать с пустым списком), а также рекурсивное правило, устанавливающее порядок перехода от обработки всего непустого списка к обработке его хвоста.

8. Сортировка списков

9. Выборка элементов из списков

10. Слияние списков

Создадим предикат, позволяющий соединить два списка в один. Первые два аргумента предиката будут представлять соединяемые списки, а третий — результат соединения.

В качестве основы для решения этой задачи возьмем рекурсию по первому списку. Базисом рекурсии будет факт, устанавливающий, что если присоединить к списку пустой список, в результате получим исходный список. Шаг рекурсии - правило, определяющее, что для того, чтобы приписать элементы списка, состоящего из головы и хвоста, ко второму списку, нужно соединить хвост и второй список, а затем к результату приписать спереди первый элемент первого списка.

conc([ ], L, L).

conc([H|T], L, [H|T1]) :– conc(T, L, T1).

Заметим, что этот предикат также можно применять для решения нескольких задач.

Во-первых, для соединения списков.

Во-вторых, для того, чтобы проверить, получится ли при объединении двух списков третий.

В-третьих, можно использовать этот предикат для разбиения списка на подсписки.

В-четвертых, можно использовать этот предикат для поиска элементов, находящихся левее и правее заданного элемента.

В-пятых, на основе нашего предиката conc можно создать предикат, находящий последний элемент списка:

last(L,X):– conc(_,[X],L).

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

member4(X,L):–

conc(_,[X|_],L).

В-седьмых, используя предикат, позволяющий объединить списки, можно создать предикат, проверяющий по двум значениям и списку, являются ли эти значения соседними элементами списка. Предикат будет иметь три параметра: первые два — значения, третий — список.

Идея решения заключается в следующем. Если два элемента оказались соседними в списке, значит, этот список можно разложить на два подсписка, причем голова второго подсписка содержит два наших элемента в нужном порядке. Выглядеть это будет следующим образом:

neighbors(X,Y,L):–

conc(_,[X,Y|_],L). /* список L получается путем

объединения некоторого списка

со списком, голову которого

составляют элементы X и Y */

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

neighbors2(X,Y,L):–

conc(_,[X,Y|_],L);

conc(_,[Y,X|_],L). /* список L получается

путем объединения некоторого

списка со списком, голову

которого составляют элементы X

и Y или элементы Y и X */

.

.