Логическое программировыание Презентация 5 Списки в Прологе. - презентация

1 Логическое программировыание Презентация 5 Списки в Прологе

2 Содержание Определение списков Структура списка Рекурсивная обработка Предикаты обработки ( примеры ) 2

3 Определение списка « Стартовое » определение : Будем называть списком упорядоченную последовательность элементов произвольной длины. задается перечислением элементов через запятую в квадратных скобках Элементами списка могут быть любые термы ( числа, символы, списки, …) Примеры списков : [a,b,c,d], [1,2,[3]], [] « Рекурсивоное » определение : Список это структура данных, определяемая следующим образом : пустой список ([ ]) является списком ; структура вида [H|T] является списком, если H первый элемент списка ( или несколько первых элементов списка, перечисленных через запятую ), а T список, состоящий из оставшихся элементов исходного списка. Принято называть H головой списка, а T хвостом списка. По - английски голова Head, а хвост Tail. операция "|" позволяет разделить список на хвост и голову 3

4 Заданное определение позволяет организовывать рекурсивную обработку списков, разделяя непустой список на голову и хвост. Хвост также является списком, содержащим меньшее количество элементов, чем исходный список. Если хвост не пуст, его также можно разбить на голову и хвост. И так до тех пор, пока мы не доберемся до пустого списка, у которого нет головы. Например, в списке [1, 2, 3] элемент 1 является головой, а список [2, 3] хвостом : ?- X = [1 | [2, 3]]. ИЛИ ?- X = [1 | [2 | [3 | [ ]]]]. X = [1, 2, 3] 4

5 Рекурсивная обработка списков Чтобы организовать обработку списка, в соответствии с приведенным выше рекурсивным определением, нам достаточно задать : предложение ( правило или факт, определяющее, что нужно делать с пустым списком ), которое будет базисом рекурсии, рекурсивное правило, устанавливающее порядок перехода от обработки всего непустого списка к обработке его хвоста. (*) Иногда базис рекурсии записывается не для пустого, а для одно - или двухэлементного списка. Определения предикатов для обработки списков обычно являются рекурсивными и со ­ стоят из двух предложений. Первое предложение определяет логические связи между аргументами предиката в тривиальном случае, задает условие окончания рекурсии. Если существует несколько случаев, то таких предложений может быть несколько. Второе предложение задает логические связи между результатом для всего списка, головой списка и результатом, полученного в ходе рекурсивного применения предиката к хвосту списка. 5

6 Предикаты для обработки списков Пример 1: предикат, позволяющий вычислить длину списка, т. е. количество элементов в списке. length([], 0). /* в пустом списке элементов нет */ length([_|T], L) :- length(T, L_T), /* L_T количество элементов в хвосте */ L = L_T + 1. /* L количество элементов исходного списка */ Проверка : ?- length([1,2,3],X). X = 3 6

7 Предикаты для обработки списков Пример 2: Предикат, позволяющий проверить принадлежность элемента списку. Предикат будет иметь два аргумента : первый искомое значение, второй список, в котором производится поиск. объект принадлежит списку, если он либо является первым элементом списка, либо элементом хвоста. member(X,[X|_]). /* X первый элемент списка */ member(X,[_|T]) :- member(X,T). /* X принадлежит хвосту T*/ Проверка : Принадлежность : ?- member(2, [1, 2, 3]). Yes Список элементов : member(X, [1, 2, 3]). X=1; X=2; X=3 Варианты списков : member(1, X). X = [1|_ ]; X = [ _, 1|_ ]; … 7

8 Оптимизация поиска Если предикат member использовать лишь для поиска элемента в списке, то можно ускорить его работу, устранив поиск элемента в хвосте списка, если он уже найден в качестве первого элемента списка. Это можно сделать двумя способами. Добавим в правило проверку на несовпадение первого элемента списка с искомым элементом, чтобы поиск элемента в хвосте списка производился только тогда, когда первый элемент списка не является искомым. member(X,[X|_]). member(X,[Y|T]):- X=\=Y, member(X,T). Добавим в факт отсечение, чтобы в ситуации, когда искомый элемент оказался первым элементом списка, не производился лишний поиск в хвосте исходного списка. member(X,[X|_]):-!. member(X,[_|T]):- member(X,T). 8

9 Предикаты для обработки списков Пример 3: предикат, позволяющий соединить два списка в один. Первые два аргумента предиката будут представлять соединяемые списки, а третий результат соединения. В качестве основы для решения этой задачи возьмем рекурсию по первому списку. Базисом рекурсии будет факт, того, что если присоединить к списку пустой список, в результате получим исходный список. Шаг рекурсии позволит создать правило - что для того, чтобы приписать элементы списка, состоящего из головы и хвоста, ко второму списку, нужно соединить хвост и второй список, а затем к результату приписать спереди первый элемент первого списка. /* при присоединении пустого списка к списку L получим список L conc([ ], L, L). /* соединяем хвост и список L, получаем хвост результата */ conc([H|T], L, [H|T1]) :- conc(T,L,T1). 9

10 Варианты использования conc для соединения списков ?- conc([1, 2, 3], [4, 5], X). X = [1, 2, 3, 4, 5] для проверки, получится ли при объединении двух списков третий ?- conc([1, 2, 3], [4, 5], [1, 2, 5]). No для разбиения списка на подсписки conc(X, [3], [1, 2, 3]). X=[1, 2]. для поиска элементов, находящихся левее и правее заданного conc(L, [2|R], [1, 2, 3, 2, 4]). L=[1], R=[3, 2, 4]; L=[1, 2, 3], R=[4] для поиска последнего элемента списка last(L,X):- conc(_,[X],L). для проверки принадлежности элемента списку member4(X,L):-conc(_,[X|_],L). 10

11 Предикаты для обработки списков Пример 4: предикат, удаляющий все вхождения заданного значения из списка. /* В пустом списке ничего не удаляем */ 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). /* Полученный в результате этих удалений список должен войти в ответ в качестве хвоста. 11

12 Сортировка списков Сортировка списка – расстановка его элементов в некотором порядке. Для определенности мы будем упорядочивать элементы списков по « неубыванию ». То есть, если сравнить любые два соседних элемента списка, то следующий должен быть не меньше предыдущего. Существует два класса алгоритмов сортировки : сортировка данных, целиком расположенных в основной памяти ( внутренняя ), и сортировка данных, хранящихся во внешней памяти ( внешняя ). Пример : внутренняя пузырьковая сортировка На каждом шаге сравниваются два соседних элемента списка. Если оказывается, что они стоят неправильно, то есть предыдущий элемент меньше следующего, то они меняются местами. Этот процесс продолжается до тех пор, пока есть пары соседних элементов, расположенные в неправильном порядке. В противном случае, список отсортирован. Аналогия с пузырьком вызвана тем, что при каждом проходе минимальные элементы как бы " всплывают " к началу списка. 12

13 Пузырьковая сортировка Реализуем пузырьковую сортировку посредством двух предикатов. Один из них будет сравнивать два первых элемента списка и в случае, если первый окажется больше второго, менять их местами. Если же первая пара расположена в правильном порядке, этот предикат будет переходить к рассмотрению хвоста. Основной предикат будет осуществлять пузырьковую сортировку списка, используя вспомогательный предикат. /* переставляем первые два элемента, если первый больше */ permutation([X,Y|T],[Y,X|T]):- X>Y,!. /*переходим к перестановкам в хвосте*/ permutation([X|T],[X|T1]):- permutation(T,T1). /* вызываем предикат, осуществляющий перестановку */ bubble(L,L1):- permutation(L,LL), !, bubble(LL,L1). /* пытаемся еще раз отсортировать полученный список */ bubble(L,L). /* если перестановок не было, значит список отсортирован */ 13