7. Обработка списков Пример 7.1. Вычисление длины списка

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

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

length([], 0). /* в пустом списке элементов нет */

length([_|T], L) :- length(T, L_T), /* L_T — количество элементов в хвосте */

L = L_T + 1. /* L — количество элементов исходного списка */

Пример 7.2. Проверка принадлежности элемента списку

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

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

member(X,[X|_]). /* X — первый элемент списка */

member(X,[_|T]) :- member(X,T). /* X принадлежит хвосту T*/

Пример 7.3. Соединение двух списков

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

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

/* при присоединении пустого списка к списку L получим список L */

conc([ ], L, L).

/* соединяем хвост и список L, получаем хвост результата */

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

Пример 7.4. Обращение списка

Разработаем предикат, позволяющий "обратить" список (записать его элементы в обратном порядке). Предикат будет иметь два аргумента: первый — исходный список, второй — список, получающийся в результате записи элементов первого аргумента в обратном порядке.

Для решения этой задачи воспользуемся рекурсией. Базис: если записать элементы пустого списка (которых нет) в обратном порядке — опять получим пустой список. Шаг рекурсии: для того чтобы получить "перевернутый" список, можно "перевернуть" его хвост и "приклеить" к нему первый элемент исходного списка. Запишем эти размышления.

/* обращение пустого списка дает пустой список*/

reverse([ ],[ ]).

/* обращаем хвост и приписываем к нему справа первый элемент исходного списка*/

reverse([X|T],Z):- reverse(T,S), conc(S,[X],Z).

Пример 7.5. Среднее арифметическое элементов списка.

В решении воспользуемся ранее определенным предикатом length для вычисления длины списка, а для вычисления суммы элементов списка определим предикат sum:

sum([], 0). /* сумма элементов пустого списка равна нулю */

sum([H|T], S) :-

sum(T, S_T), /* S_T — сумма элементов хвоста */

S is S_T + H. /* S — сумма элементов исходного списка */

Для нахождения среднего нам достаточно будет сумму элементов списка разделить на их количество. Это можно записать следующим образом:

avg(L,A):-

summa(L,S), /* помещаем в переменную S сумму элементов списка */

length(L,K), /* переменная K равна количеству элементов списка */

A is S/K. /* вычисляем среднее как отношение суммы к количеству */

Пример 7.6. Удаление дубликатов из списка

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

Если первый элемент окажется удаляемым, то нужно перейти к удалению заданного значения из хвоста списка. Результатом в данном случае должен стать список, полученный путем удаления всех вхождений искомого значения из хвоста первоначального списка. Это даст нам базис рекурсии. Шаг рекурсии будет основан на том, что если первый элемент списка не совпадает с тем, который нужно удалять, то он должен остаться первым элементом результата, и нужно переходить к удалению заданного значения из хвоста исходного списка. Полученный в результате этих удалений список должен войти в ответ в качестве хвоста.

delete_all(_,[],[]).

delete_all(X,[X|L],L1):–

delete_all (X,L,L1).

delete_all (X,[Y|L],[Y|L1]):–

X=\=Y,

delete_all (X,L,L1).