Поиск заданного элемента
Объединение списков.
Генерирование списка из (N2-N1) последовательных целых чисел, начиная с N1.
Для формирования списка создадим отношение genlist(N1, N2, L), где
N1 – начальный элемент списка
N2 – его верхняя граница
L – список
Возможны случаи:
1) если N1 = N2, тогда N1 – не добавляется в список и L – пустой список.
genlist (N2, N2, [ ]) – первая часть правила (условие останова).
2) если N1 < N2, то N1 помещаем в голову списка, затем увеличиваем N1 на 1 и для нового значения снова вызывается genlist. Получаем вторую часть правила:
genlist (N1, N2, [N1 | L]): - N1 < N2, N = N1+1, genlist (N, N2, L).
Таким образом, правило формирования списка имеет вид:
genlist (N2, N2, [ ]). % нерекурсивная часть правила
genlist (N1, N2, [N1 | L]): - % рекурсивная часть правила
N1 < N2, N = N1+1, GenList (N, N2, L).
Например, для формирования списка [2, 3, 4, 5] следует указать запрос:
GOAL
GenList (2, 6, L), Write (L), nl.
Создадим отношение append(L1, L2, L3), где L1, L2 – исходные списки, L3 – список, полученный в результате присоединения L2 к L1.
Возможны случаи:
1) если L1 пустой список, то результирующий список L3 равен списку L2. Получаем первую (нерекурсивную) часть правила:
append ([ ], L, L).
2) если L1 не пустой список, то делим его на голову и хвост ( [X | L1]). Вторая (рекурсивная) часть правила:
append ([X | L1], L2, [X | L3]): - append (L1, L2, L3).
Таким образом, правило объединения списков имеет вид:
append ([ ], L, L).
append ([X | L1], L2, [X | L3]): - append (L1, L2, L3).
Например, для объединения списков [1, 2, 3] и [4, 5] следует написать запрос:
GOAL
append ([1, 2, 3], [4, 5], L) write [L].
Результат:
[1, 2, 3, 4, 5]
При выполнении программы из L1 выделяется и заносится в стек по одному элементу (голова списка) до тех пор, пока L1 не станет пустым. После этого выполняется первая часть правила и L3 получает значение L2, то есть L3 = [4, 5] начинается выгрузка элементов из стека и добавление их в голову L3.
Правило appendобладает большое гибкостью и позволяет решать множество задач по обработке списка. Его можно использовать для решения обратной задачи: разбиение исходного списка на две части.
Например, чтобы определить все возможные способы разбиения списка [1,2,3], следует составить запрос:
GOAL
append (L1, L2, [1,2,3]), write (“L1=”, L1, “L2=”, L2), fail, nl.
Результат:
L1 = [ ] L2 = [1, 2, 3]
L1 = [1] L2 = [2, 3]
L1 = [1, 2] L2 = [3]
L1 = [1, 2, 3] L2 = [ ]
Чтобы определить содержится ли элемент X в списке L создадим отношение member(X, L).
Возможны случаи:
1) если X совпадает с головой списка L, то элемент найден и поиск прекращается. Первая часть правила (нерекурсивная):
member (X, [X | L]).
2) если X не принадлежит голове, то он может принадлежать хвосту. Отбрасываем голову списка и вызываем правило для оставшегося списка. Вторая часть правила (рекурсивная):
member (X, [_ | L]: - member (X, L).
Таким образом, правило поиска элемента имеет вид:
member (X, [X | L]).
member (X, [_ | L]: - member (X, L).
Например, для ответа на вопрос «Содержится ли число 4 в списке [2, 3, 4, 5]?», можно составить запрос:
GOAL
member(4, [2, 3, 4, 5]),Write (“yes”);Write (“no”), nl.
При выполнении поиска X сравнивается с головой L. Если элементы не совпадают, то первый элемент отбрасывается и X сравнивается с головой полученного списка и так далее, пока L не станет пустым списком. Если элемент X найден, то цель достигнута, выводится сообщение “yes”, иначе выводится “no”.