Работа со списками в Прологе.
Списки в Прологе.
В Прологе основным составным типом данных является список. Под списком понимается упорядоченная последовательность элементов произвольной длины. Список задается перечислением элементов списка через запятую в квадратных скобках, так, как показано в приведенных ниже примерах.
[1,2,3,4,5] – список целых чисел;
[“one”,”two”,”three”] – список строк;
[] – пустой список, не содержащий ни одного элемента.
Элементы списка могут быть любыми, в том числе и составными объектами. В частности, элементы списка сами могут быть списками.
В разделе описания доменов списки описываются следующим образом:
DOMAINS
<имя спискового домена>=<имя домена элементов списка>*
Звездочка после имени домена указывает на то, что мы описываем список, состоящий из объектов соответствующего типа.
Например:
listI = integer* /* список, элементы которого —
целые числа */
listR = real* /* список, состоящий из вещественных чисел */
listC = char* /* список символов */
listS = string* /* список, состоящий из строк */
listL = listI* /* список, элементами которого являются списки целых чисел */
Последнему примеру будут соответствовать списки вида:
[[1,2,4],[5],[3,-8,94],[]].
Можно дать рекурсивное определение списка следующим образом:
1. пустой список ( [ ] ) является списком;
2. структура вида [H|T] является списком, если H — первый элемент списка (или несколько первых элементов списка, перечисленных через запятую), а T — список, состоящий из оставшихся элементов исходного списка.
|
|
|
Данное определение позволяет организовывать рекурсивную обработку списков, разделяя непустой список на голову и хвост. Например, в списке [1, 2, 3] элемент 1 является головой, а список [2, 3] — хвостом, т.е. [1, 2, 3] = [1|[2, 3]]. Хвост этого списка [2, 3], в свою очередь, может быть представлен в виде головы 2 и хвоста [3], а список [3] можно рассматривать в виде головы 3 и хвоста []. Пустой список далее не разделяется. В итоге получаем, что список [1, 2, 3] эквивалентен списку [1|[2, 3]], который, в свою очередь, эквивалентен списку [1|[2|[3]]]. Последний сопоставим со списком [1|[2|[3|[ ]]]]. В этом же списке можно выделить два первых элемента и хвост из третьего элемента [1,2|[3]]. И, наконец, возможен вариант разбиения на голову из трех первых элементов и пустой хвост: [1, 2, 3|[]].
Чтобы организовать обработку списка, в соответствии с приведенным выше рекурсивным определением, достаточно задать предложение (правило или факт, определяющее, что нужно делать с пустым списком), которое будет базисом рекурсии, а также рекурсивное правило, устанавливающее порядок перехода от обработки всего непустого списка к обработке его хвоста. Иногда базис рекурсии записывается не для пустого, а для одно- или двухэлементного списка.
|
|
|
Алгоритмы обработки списков
1. Вывод элементов списка на экран
Предикат, позволяющий распечатать список, можно задать следующим образом:
printlist ([ ]):- !. /*если список пустой, печать ничего не надо и работа должна быть остановлена – используем отсечение */
printlist ([H | T]):- write (H), nl, printlist (T). /*у непустого списка печатаем голову, затем рекурсивно вызываем наш предикат для печати хвоста списка*/
2. Вычисление длины списка
Создадим предикат, позволяющий вычислить длину списка, т.е. количество элементов в списке. Для решения этой задачи воспользуемся очевидным фактом, что в пустом списке элементов нет, а количество элементов непустого списка, представленного в виде объединения первого элемента и хвоста, равно количеству элементов хвоста, увеличенному на единицу. Запишем эту идею:
length([], 0). /* в пустом списке элементов нет */
length([_|T], L) :–
length(T, L_T), /* L_T — количество
элементов в хвосте */
L = L_T + 1. /* L — количество элементов
исходного списка */
Обратите внимание, что при переходе от всего списка к его хвосту нам не важно, чему равен первый элемент списка, поэтому мы используем анонимную переменную.
|
|
|
3. Поиск элемента в списке
Напишем предикат, позволяющий проверить принадлежность элемента списку. Предикат будет иметь два аргумента: первый — искомое значение, второй — список, в котором производится поиск.
Построим данный предикат, опираясь на тот факт, что объект принадлежит списку, если он либо является первым элементом списка, либо элементом хвоста. Это может быть записано в виде двух предложений:
member(X,[X|_]). /* X — первый элемент списка */
member(X,[_|T]) :–
member(X,T). /* X принадлежит хвосту T*/
Заметим, что в первом случае (когда первый элемент списка совпадает с исходным элементом), нам не важно, какой у списка хвост, и можно в качестве хвоста указать анонимную переменную. Аналогично, во втором случае, если X принадлежит хвосту, нам не важно, какой элемент первый.
Описанный предикат можно использовать для решения сразу трех задач: во-первых, конечно, для того, для чего мы его и создавали, т.е. для проверки, имеется ли в списке конкретное значение. Мы можем, например, поинтересоваться, принадлежит ли двойка списку [1, 2, 3]:
member(2, [1, 2, 3]).
Получим, естественно, ответ: "Yes".
Подобным образом можно спросить, является ли число 4 элементом списка [1, 2, 3]:
|
|
|
member(4, [1, 2, 3]).
Ответом, конечно, будет "No".
Второй способ использования данного предиката — это получение по списку его элементов. Для этого нужно в качестве первого аргумента предиката указать свободную переменную. Например:
member(X, [1, 2, 3]).
В качестве результата получим список всех элементов списка:
X=1
X=2
X=3
Третий способ позволит получить по элементу варианты списков, которые могут его содержать. Теперь свободную переменную запишем вторым аргументом предиката, а первым — конкретное значение. Например,
member(1, X).
Вначале Пролог-система выдаст предупреждение о том, что переменная X не связана в первом предложении ( "708 WARNING: The variable is not bound in this clause. (F10=ok, Esc=abort)" ). У нас есть два способа отреагировать на это предупреждение: нажать кнопку Esc, чтобы отказаться от генерации списков, содержащих единицу в качестве элемента; нажать F10 для того, чтобы продолжить выполнение цели. Во втором случае Пролог-система начнет выдавать варианты списков, содержащих единицу:
X=[1|_] /* единица — первый элемент списка */
X=[_,1|_] /* единица — второй элемент списка */
X=[_,_,1|_] /* единица — третий элемент списка */
и т.д.
Этот процесс будет продолжаться до тех пор, пока не будет нажата комбинация клавиш Ctrl+Break.
Если данный предикат планируется использовать только первым способом, то можно ускорить его работу, устранив поиск элемента в хвосте списка, если он уже найден в качестве первого элемента списка. Это можно сделать двумя способами.
Первый способ. Добавим в правило проверку на несовпадение первого элемента списка с искомым элементом, чтобы поиск элемента в хвосте спискапроизводился только тогда, когда первый элемент списка не является искомым. Модифицированный предикат будет выглядеть следующим образом:
member2(X,[X|_]).
member2(X,[Y|T]):–
X<>Y, member2(X,T).
Эту модификацию предиката member нельзя использовать для получения всех элементов списка. Потому, что при попытке согласования подцели свободная переменная X будет сравниваться с неозначенной переменной Y. Получим сообщение об ошибке "Free variable in expression".
Второй способ. Добавим в факт отсечение, чтобы при нахождении элемента в голове списка, не производился дальнейший поиск в хвосте. Получим:
member3(X,[X|_]):–!.
member3(X,[_|T]):–
member3(X,T).
Хотя эта модификация предиката member более эффективна, чем исходная, ее можно использовать только для того, чтобы проверить, имеется ли в списке конкретное значение. Если мы попытаемся применить ее для получения всех элементов списка, подставив в качестве первого аргумента несвязанную переменную, то результатом будет только первый элемент списка. Отсечение не позволит нам получить оставшиеся элементы.
4. Объединение списков
Создадим предикат, позволяющий соединить два списка в один. Первые два аргумента предиката будут представлять соединяемые списки, а третий — результат объединения. Идея алгоритма будет состоять в последовательном отделении голов от первого списка, пока не получим пустого списка, и обратной «сборке» - присоединения по порядку ко второму списку последних отделенных голов первого списка. Базисом рекурсии будет факт, устанавливающий, что если присоединить к списку пустой список, в результате получим исходный список. Шагом рекурсии будет служить правило, определяющее, что для того, чтобы приписать элементы списка, состоящего из головы и хвоста, ко второму списку, нужно соединить хвост и второй список, а затем к результату приписать спереди первый элемент первого списка. Запишем решение:
conc([ ], L, L). /* при присоединении пустого списка
к списку L получим список L */
conc([H|T], L, [H|T1]) :–
conc(T,L,T1). /* голова объединенного списка совпадает с головой первого списка, а хвост есть результат объединения хвоста первого списка со вторым */
Этот предикат также можно применять для решения нескольких задач. Во-первых, для соединения списков. Например, если задать вопрос
conc([1, 2, 3], [4, 5], X)
то получим в результате
X= [1, 2, 3, 4, 5]
Во-вторых, для того, чтобы проверить, получится ли при объединении двух списков третий. Например, на вопрос:
conc([1, 2, 3], [4, 5], [1, 2, 5]).
ответом будет, конечно, No.
В-третьих, можно использовать этот предикат для разбиения списка на подсписки. Например, если задать следующий вопрос:
conc([1, 2], Y, [1, 2, 3]).
то ответом будет Y=[3].
Аналогично, на вопрос
conc(X, [3], [1, 2, 3]).
получим ответ X=[1, 2].
И, наконец, можно спросить
conc(X, Y, [1, 2, 3]).
Получим четыре решения:
X=[], Y=[1, 2, 3]
X=[1], Y=[2, 3]
X=[1, 2], Y=[3]
X=[1, 2, 3], Y=[]
В-четвертых, можно использовать этот предикат для поиска элементов, находящихся левее и правее заданного элемента. Например, если нас интересует, какие элементы находятся левее и, соответственно, правее числа 2, можно задать следующий вопрос:
conc(L, [2|R], [1, 2, 3, 2, 4]).
Получим два решения:
L=[1], R=[3, 2, 4].
L=[1, 2, 3], R=[4]
В-пятых, на основе предиката conc можно создать предикат, находящий последний элемент списка:
last(L,X):–
conc(_,[X],L).
Конечно, этот предикат можно было написать и без использования предиката conc:
last2([X],X). /* единственный элемент списка является последним */
last2([_|L],X):–
last2(L,X). /* последний элемент любого списка совпадает
с последним элементом хвоста этого списка */
В-шестых, можно определить, используя conc, предикат, позволяющий проверить принадлежность элемента списку. При этом воспользуемся тем, что если элемент принадлежит списку, то список может быть разбит на два подсписка так, что искомый элемент является головой второго подсписка:
member4(X,L):–
conc(_,[X|_],L).
В-седьмых, используя предикат, позволяющий объединить списки, можно создать предикат, проверяющий по двум значениям и списку, являются ли эти значения соседнимиэлементами списка. Предикат будет иметь три параметра: первые два — значения, третий —список.
Идея решения заключается в следующем. Если два элемента оказались соседними в списке, значит, этот список можно разложить на два подсписка, причем голова второго подсписка содержит два наших элемента в нужном порядке. Выглядеть это будет следующим образом:
neighbors(X,Y,L):–
conc(_,[X,Y|_],L). /* список L получается путем
объединения некоторого списка
со списком, голову которого
составляют элементы X и Y */
Обратите внимание, что этот предикат проверяет только наличие нужных значений в указанном порядке. Если нам неважен порядок, в котором два данных значения встречаются в некотором списке, то следует записать модификацию описанного выше предиката, которая будет проверять оба варианта размещения искомых элементов. Для этого достаточно, чтобы список раскладывался на два подсписка, причем голова второго подсписка содержала два наших элемента либо в прямом, либо в обратном порядке. Соответствующий программный код будет следующим:
neighbors2(X,Y,L):–
conc(_,[X,Y|_],L);
conc(_,[Y,X|_],L). /* список L получается
путем объединения некоторого
списка со списком, голову
которого составляют элементы X
и Y или элементы Y и X */
5. Получение элемента с заданным номером
Напишем предикат, позволяющий получать элементсписка по его номеру так же, как по номеру - индексу можно получать элемент массива в императивных языках программирования. Предикат будет трехаргументный: первый аргумент — исходный список, второй аргумент — номер элемента и третий — выходной аргумент, элемент списка, указанного в качестве первого аргумента предиката, имеющий номер, указанный в качестве второго аргумента. Проведем рекурсию по номеру элемента. В качестве базиса рекурсии запишем тот факт, что элементом с номером 1 является его голова. Шагом рекурсии сделаем правило, определяющее, что номер элемента в списке на единицу меньше, чем номер этого элемента в хвосте списка. Получим процедуру:
get_n([X|_],1,X).
get_n([_|L],N,Y):–
N1=N–1,
get_n(L,N1,Y).
6. Вычисление суммы элементов списка
Создадим предикат, позволяющий вычислять сумму элементов списка. Предикат будет иметь два аргумента – список и требуемую сумму. В качестве базиса рекурсии укажем факт, что сумма элементов пустого списку равна нулю. В шаге рекурсии опишем правило, прибавляющее голову списка к сумме хвоста списка.
sum([], 0). /* сумма элементов пустого списка равна
нулю */
sum([H|T], S) :–
sum(T, S1), /* вычислим S1 — сумму элементов хвоста */
S = S1 + H. /* тогда результат S есть сумма головы и S1*/
Достаточно часто требуется вычислить сумму не всех элементов, а только удовлетворяющих некоторому условию. Например, модифицируем предикат таким образом, чтобы он находил сумму элементов списка, кратных трем.
sum2([],0).
sum2([H|T],S):-
(H mod 3) =0,!,
sum(T,S1),
S = S1 + H.
sum2([_|T],S):-
sum(T,S).
Во втором предикате добавили проверку головы на кратность трем и поставили отсечение, благодаря которому третье правило будет вызываться только в случае, если голова списка не кратна трем. В этом случае искомая сумма будет совпадать с суммой хвоста списка, а значение головы списка нам не важно, используем анонимную переменную.
Другой вариант данного предиката можно написать, используя дополнительный аргумент - накопитель. В нем будем хранить уже насчитанную сумму. Начинаем с пустым накопителем. Переходя от вычисления суммы непустого списка к вычислению суммы элементов его хвоста, будем добавлять первый элемент к уже насчитанной сумме. Когда элементы списка будут исчерпаны (список опустеет), передадим "накопленную" сумму в качестве результата в третий аргумент. Запишем:
sum3([],S,S). /* список стал пустым, значит
в накопителе — сумма элементов
списка */
sum3([H|T],N,S) :–
N_T=H+N,
/* N_T — результат добавления к сумме,
находящейся в накопителе, первого
элемента списка */
sum3(T,N_T,S).
/* вызываем предикат от хвоста T и N_T */
Если нам нужно вызвать предикат от двух аргументов, а не от трех, то можно добавить вспомогательный предикат:
summa(L,S):–
sum3(L,0,S).
Последний вариант, в отличие от первого, реализует хвостовую рекурсию.
7.Удаление элемента из списка
Приведем пример предиката, удаляющего все вхождения заданного значения из списка. Предикат будет зависеть от трех параметров. Первый параметр будет соответствовать удаляемому списку, второй — исходному значению, а третий — результату удаления из первого параметра всех вхождений второго параметра. В качестве базиса рекурсии используем тот элементарный факт, что результатом удаления чего бы то ни было из пустого списка, окажется пустой список. Далее рассмотрим две ситуации. Если голова списка совпадает с удаляемым элементом – результатом должен быть список, полученный дальнейшим удалением элементов из хвоста. Иначе голова списка переписывается, а к хвосту снова применяется рекурсивный вызов.
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).
Если же нам нужно удалить не все вхождения определенного значения в список, а только первое, то следует немного изменить вышеописанную процедуру. Это можно сделать, заменив в первом правиле рекурсивный вызов предиката отсечением. В этом случае, пока первый элемент списка не окажется удаляемым, мы будем переходить к рассмотрению хвоста.
delete_one(_,[],[]).
delete_one(X,[X|L],L):–!.
delete_one(X,[Y|L],[Y|L1]):–
delete_one(X,L,L1).
8. Нахождение максимального элемента списка
Создадим предикат, находящий максимальный элемент списка. Предикат будет иметь два аргумента – список и результат, максимальный элемент. Базис рекурсии запишем не для пустого, а для одноэлементного списка – результат будет равен единственному элементу списка. Правило, соответствующее шагу рекурсии, будет сравнивать голову списка и максимальный элемент хвоста, и выбирать из них наибольший с помощью предиката max, описанному в . Процедура выглядит так:
max_list([X],X). /* единственный элемент списка является максимальным */
max_list([H|T],M):–
max_list(T,M_T), /* M_T — максимальный элемент хвоста */
max(H,M_T,M). /* M — максимум из M_T и первого элемента
исходного списка */
Аналогично, процедура для нахождения минимального элемента будет выглядеть так:
min_list([X],X).
min_list([H|T],M):–
min_list(T,M_T),
min(H,M_T,M).
Последний предикат min для нахождения минимального значения из двух элементов предлагаем читателю написать самостоятельно.
Алгоритмы сортировки
Под сортировкой обычно понимают расстановку элементов в некотором порядке. Для определенности мы будем упорядочивать элементы списков по неубыванию. То есть, если сравнить любые два соседних элемента списка, то следующий должен быть не меньше предыдущего.
Рассмотрим наиболее известные методы сортировки и особенности их реализации в Прологе. Начнем с наиболее известного "пузырькового" способа сортировки. Его еще называют методом прямого обмена или методом простого обмена.
Пузырьковая сортировка
Идея этого метода заключается в следующем. На каждом шаге сравниваются два соседних элемента списка. Если оказывается, что они стоят неправильно, то есть предыдущий элемент меньше следующего, то они меняются местами. Этот процесс продолжаем до тех пор, пока есть пары соседних элементов, расположенные в неправильном порядке. Это и будет означать, что список отсортирован. Аналогия с пузырьком вызвана тем, что при каждом проходе минимальные элементы как бы "всплывают" к началу списка.
Реализуем пузырьковую сортировку с помощью двух предикатов. Первый, назовем его permutation, будет сравнивать два первых элемента списка и в случае, если первый окажется больше второго, менять их местами. Если же первая пара расположена в правильном порядке, этот предикат будет переходить к рассмотрению хвоста. Фактически, этот предикат будет осуществлять один проход по списку и переставлять максимальный элемент в конец списка. Основной предикат bubble будет вызывать вспомогательный предикат permutation до тех пор, пока весь список не будет отсортирован.
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). /* если перестановок не было, значит список
отсортирован */
Первое правило bubble работает только до тех пор, пока есть хотя бы пара элементов списка, расположенных в неправильном порядке. Как только такие элементы закончились, предикат permutation терпит неудачу, а bubble переходит от правила к факту и возвращает в качестве второго аргумента отсортированный список.
Сортировка вставкой
Теперь рассмотрим сортировку вставкой. Она основана на том, что если хвост списка уже отсортирован, то достаточно поставить первый элемент списка на нужное место в хвосте, и весь список будет отсортирован. Для реализации этой идеи создадим два предиката. Задача предиката insert — вставить значение (голову исходного списка) в уже отсортированный список (хвост исходного списка), так чтобы он остался упорядоченным. Его первым аргументом будет вставляемое значение, вторым — отсортированный список, третьим — список, полученный вставкой первого аргумента в нужное место второго аргумента так, чтобы не нарушить порядок. Предикат ins_sort, собственно, и будет организовывать сортировку исходного списка методом вставок. В качестве первого аргумента ему дают произвольный список, который нужно отсортировать. Вторым аргументом он возвращает список, состоящий из элементов исходного списка, стоящих в правильном порядке.
ins_sort([ ],[ ]). /* отсортированный пустой список
остается пустым списком */
ins_sort([H|T],L):–
ins_sort(T,T_Sort),
/* T — хвост исходного списка,
T_Sort — отсортированный хвост
исходного списка */
insert(H,T_Sort,L).
/* вставляем H (первый элемент
исходного списка)в отсортированный хвост T_Sort,
получаем окончательный результат L */
insert(X,[],[X]). /* при вставке любого значения в пустой
список, получаем одноэлементный
список */
insert(X,[H|T],[H|T1]):–
X>H,!, /* если вставляемое значение
больше головы списка, значит
его нужно вставлять в хвост */
insert(X,T,T1).
/* вставляем X в хвост T,
в результате получаем
список T1 */
insert(X,T,[X|T]). /* это предложение (за счет отсечения
в предыдущем правиле) выполняется,
только если вставляемое значение
не больше головы списка T, значит,
добавляем его первым элементом
в список T */
Сортировка выбором
Идея алгоритма сортировки выбором состоит в следующем. В списке находим минимальный элемент (используя предикат min_list, который описан в предыдущей главе). Удаляем его из списка (с помощью предиката delete_one, рассмотренного также в предыдущей главе). Оставшийся список сортируем. Приписываем минимальный элемент в качестве головы к отсортированному списку. Так как этот элемент был меньше всех элементов исходного списка, он будет меньше всех элементов отсортированного списка. Запишем процедуру:
choice([ ],[ ]). /* отсортированный пустой список
остается пустым списком */
choice(L,[X|T]):– /* приписываем X (минимальный элемент
списка L) к отсортированному
списку T */
min_list(L,X), /* X — минимальный элемент
списка L */
delete_one(X,L,L1),
/* L1 — результат удаления
первого вхождения
элемента X из списка L */
choice(L1,T). /* сортируем список L1,
результат обозначаем T */
Быстрая сортировка
Идея метода заключается в следующем. Выбирается некоторый "барьерный" элемент, относительно которого мы разбиваем исходный список на два подсписка. В один мы помещаем элементы, меньшие барьерного элемента, во второй — большие либо равные. Каждый из этих списков мы сортируем тем же способом, после чего приписываем к списку тех элементов, которые меньше барьерного, вначале сам барьерный элемент, а затем — список элементов не меньших барьерного. В итоге получаем список, состоящий из элементов, стоящих в правильном порядке.
Вспомогательный предикат partition будет отвечать за разбиение списка на два подсписка. У него будет четыре аргумента. Первые два элемента — входные: первый — исходный список, второй — барьерный элемент. Третий и четвертый элементы — выходные, соответственно, список элементов исходного списка, которые меньше барьерного, и список, состоящий из элементов, которые не меньше барьерного элемента.
Непосредственно сама сортировка будет осуществляться с помощью предиката quick_sort. Он будет состоять из двух предложений. Правило будет осуществлять с помощью предиката partition разделение непустого списка на два подсписка, затем сортировать каждый из этих подсписков рекурсивным вызовом себя самого, после чего, используя предикат conc (см. главу 5.1), сопоставляет второму аргументу список, получаемый объединением отсортированного первого подсписка и списка, сконструированного из барьерного элемента (головы исходного списка) и отсортированного второго подсписка. Запишем это:
quick_sort([],[]). /* отсортированный пустой список
остается пустым списком */
quick_sort([H|T],O):–
partition(T,H,L,G),
/* делим список T на L (список
элементов меньших барьерного
элемента H) и G (список
элементов не меньших H) */
quick_sort(L,L_s),
/* список L_s — результат
упорядочивания элементов
списка L */
quick_sort(G,G_s),
/* аналогично, список G_s —
результат упорядочивания
элементов списка G */
conc(L_s,[H|G_s],O).
/* соединяем список L_s со
списком, у которого голова H,
а хвост G_s, результат
обозначаем O */
partition([],_,[],[]). /* как бы мы ни делили элементы
пустого списка, ничего кроме
пустых списков не получим */
partition([X|T],Y,[X|T1],Bs):–
X<Y,!,
partition(T,Y,T1,Bs).
/* если элемент X меньше барьерного
элемента Y, то мы добавляем его
в третий аргумент */
partition([X|T],Y,T1,[X|Bs]):–
partition(T,Y,T1,Bs).
/* в противном случае дописываем
его в четвертый аргумент */
Дата добавления: 2019-03-09; просмотров: 4692; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!