Операции над списками в ПРОЛОГе

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

Разделение на голову и хвост. Операция осуществляется | (вертикальной чертой )

[Head|Tail]

Пример: вывод элементов списка

Domains.

List=integer*

Predicates

Print_list(list)

Clauses

Print_list([])./*условие прекращения реурсии*/

Print_list([H | T]):- write (H),nl,

Print_list(T).

2-я клауза срабатывает до тех пор, пока Т не станет пустым списком, тогда срабатывает первая(прекращение рекурсии).

Поиск элементов в списке. Очевидно предикат должен иметь 2 аргумента:

1)что искать;

2)список, в котором надо искать.

B= number*

Number=integer

Predicates

Find(H,[H|-]).

Find(H,[-|T]):-

Find(H,T).

1-я клауза срабатывает, когда искомый элемент является 1-й в списке, если нет - производится рекурсивный вызов для списка является хвостом.

Деление списков. Пусть необходимо разделить список на 2: в одном элементы меньше порога, в другом - больше.

Идея работы: из исходного списка выделяется голова, включается в 1-й или во 2 -й список до исчерпания исходного списка.

domains

M=integer

List = integer*

predicates

split (M, List, List,List)

clauses

split (M, [M/T], [M/L1], L2: - H<M, split (M, T, L1,t1))

split (M, [H/T], L1, [H/L2]): - H>M, split (M, T, L1,L2)

split ( _, [ ], [ ], [ ]. (split ( _, [], _, _).)

split (40, [30, 50, 20, 25, 65, 95], Ls1, Ls2)

   Означивание переменных происходит не только при сопоставлении подцелей, но и при сопоставлении заголовка. В данном случае, означивается М как 40, Н - как 30, делается попытка представить первый результирующий список в виде головы и хвоста, но голова при этом уже известна. Это соответствует попытке прилепить голову к неизвестному списку L1. Коль скоро это невозможно (L1 сцеплен с Ls1 и не определен), то действие отклоняется в стек. Проводится условие H<M и выполняется рекурсивный вызов с хвостом списка. Если H<M не согласовывается, все подстановки и означивания отменяются, главный маркер переходит на вторую клаузу. Все повторяется, но голова прилепляется к списку L2. Рекурсивный вызов первой и второй клауз продолжается до тех пор, пока исходный список не станет пустым. В этом случае ни 1-ая, ни 2-ая клауза не могут быть сопоставлены (у пустого списка голову и хвост не выделяют). Срабатывает 3-я клауза. При этом L1 и L2 означиваются как пустые списки. Начинается сворачивание рекурсии, из стека извлекаются очередные значения головы и выполняются отложенные действия: присоединение головы либо к L1, либо к L2. Если результирующие списки не пусты, то в 3-ей клаузе вместо 3-го и 4-го аргументов для успеха сопоставления следует поставить подчерки.

Присоединение списка. Список L1 необходимо присоединить к списку L2, создав список L3, который в начале пустой.

domains

list = integer*          

predicates

app (list, list, list,)

clauses

app ([], L, L)

app ([N/L1], L2, [N/L3]): - app (L1, L2, L3)

L1 = [1, 2, 3]

L2 = [4, 5, _]

L3 = [ ]

   При срабатывании 1-ой клаузы неозначенная переменная L означивается как L2, затем означивает L3 как L2, и начинается сворачивание рекурсии: к L3 = L2 поочередно добавляются головы 3, 2, 1.

Компоновка данных в список. Для решения этой задачи существует встроенный предикат с таким предописанием:

findall (<объект входного предиката>,

<входной предикат>,

<имя выходного списка>)

Пример: пусть есть статическая база данных об очках футбольных команд

predicates

football (name, points)

clauses

football (“kom1”, 10).

Football (“kom2”, 7).

........

football (“kom10”, 2).

........

findall (Points, football (-, Points), Points.list)

 [10, 7, ..., 2]

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

Пример: посимвольная запись символов с клавиатуры

clauses

creat_file: -

nl, write (“Введите имя файла”), nl,

readln (Filename),

openwrite (df, Filename),

writedevice (df),

readchar (c),

r_w_c (c)

closefile (df).

r_w_c (‘#’):- !. /*конец*/

r_w_c (‘\13’):-

write (‘\13\10’),

readchar (c1)

r_w_c (c1)

.........