Изображение и обработка списков

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

[a, b, c, e, f], [7, 4, -3, 5].

Элементы списка разделяются запятой, а их типы определяются соответствующей записью в разделе domains

domains

list1 = symbol*

list2 = integer*.

Так первая запись означает, что список типа list1 состоит из символов, а типа list2 – из целых чисел. В разделе предикатов должны быть соответствующие описания

pred1 (list1)

pred2 (list2).

Списки могут быть простыми, как приведенные выше, и сложными, например,

[3, [8, 9], 2, -1, [5, 4, 9],...].

В этом случае объявление списка имеет вид

domains

list = integer*

ll = list*.

В Прологе реализовано встроенное средство работы со списками. Список автоматически разбивается на две части путем записи

[H|T]

где Н обозначает голову списку (head), а T – его хвост (tail). Голова списка является элементом и, в зависимости от структуры, может быть тоже списком. Так, для списка [[a, b], e, t, k] имеем

H = [a, b], T = [e, t, k].

Хвост всегда является списком. Список, который не содержит ни одного элемента, называется пустым и обозначается как [ ]. Так, константа а и список [a] есть два разных объекта, поскольку этот список может быть изображен как [a|[]]. Попытка разбить пустой список на хвост и голову всегда приводить к неудаче. С приведенного определения вытекает, что концептуально список имеет древовидную структуру, которая для списка [a, b, c] может быть изображена так (рис 1).

Рис 1.

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

member([E|_], E).

member([_|T], E): - member(T, E).

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

delete ([], [], _).

delete ([H|T], [H|T1], E): - E< > H, delete (T, T1, E).

delete ([E|T], T1, E): - delete (T, T1, E).

Рассмотрим действие правила на примере списка L = [a, f, b, c, f], из которого нужно удалить все вхождения элемента f

Фаза редукции Фаза решения

R₃ = [a| R₂] R =[a, b, c]

R₂ = [b| R₁] R₂ =[b, с]

R₁= [c| R₀] R₁ =[c]

R₀ = [ ]

Изъять элемент – значит не присоединить его к хвосту списка-результата. Первое правило осуществляет простое копирование входного списка в список-результат, когда голова не равна заданному элементу.

По определению рекурсивных вычислений граничным условием является задача, решение которой известно. Вычислим длину списка (количество его элементов). Так как длина пустого списка равна нулю, граничным условием будет

len ([], 0).

При каждом рекурсивном вызове правила (обращении к длине хвоста), длина списка увеличивается на единицу, при этом значение элемента-головы не является существенным.

len ([_|T], L): - len (T, K), L = K+1.

Правило для вычисления суммы элементов списка будет совершенно аналогичным предыдущему с единственным отличием, значение головы списка необходимо для вычисления суммы.

sum ([], 0).

sum (H|T], R): - len (T, S), R = S+H.