Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Лекции ФЛП.doc
Скачиваний:
18
Добавлен:
27.05.2015
Размер:
632.83 Кб
Скачать

Лекция 4

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

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

[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

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

R3= [a|R2]R=[a,b,c]

R2= [b|R1]R2=[b,с]

R1= [c| R0] R1=[c]

R0= [ ]

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

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

len ([], 0).

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

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

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

sum ([], 0).

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

Объединение списков.

append(list, list, list).

append([], L, L).

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

Предикат append принадлежит к классу предикатов, аргументы которых могут быть инвертированы по смыслу.

append([1,2,3], [4,5], X) X=[1,2,3, 4,5]

append(1,2,3], X, [1,2,3,4,5]) X=[ 4,5]

append(X, [4,5], [1,2,3, 4,5]) X=[1,2,3]

Для целевого утверждения append(X, Y, [1,2,3]) получим следующие решения

X1=[] Y1=[1,2,3]

X2=[1] Y2=[2,3]

X3=[1,2,3] Y3=[]

Легко видеть, что разные решения получаем в зависимости от того, с какими значениями аргументов происходит сопоставление целевого утверждения и граничного условия.

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

get_list ([H|T]):- write (“input element”), readint (H), H<>666, get_list(T).

get_list([]).

Если бы предельное условие было на первом месте, то при обращении к этому правилу get_list(X) мы бы получили X=[ ], так как при обращении к рекурсивной части правила была бы попытка разбить пустой список на хвост и голову.

Определение всех решений вместе. При работе с недетерминированными предикатами довольно часто возникает необходимость иметь все решения одновременно. Очевидно, что наиболее удобной структурой для их размещения будет список. Для этой цели существует стандартный предикат findall(предикат, переменная, список).

Например, пусть имеем задачу, в которой необходимо вычислить среднюю годовую прибыль группы людей, информация о прибыли каждого из которых записана в форме предиката worker(name, sum). Тогда эта задача будет сформулирована в виде следующего правила

middl_sum(Y):-findall(worker(_,X), X, List), len(List, N), sum(List, S),Y=S/N.

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]