Основы программирования на языке Turbo Prolog

Процесс повторяется до тех пор, пока это утверждение дает либо успех в случае установления соответствия на очередной рекурсии, либо неуспех в случае исчерпания списка.

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

/* Программа 6.3 «Элементы». Назначение:       */

/* поиск  нужного элемента в списке.          */

domains

 

   number_list = integer *

   person_list = symbol *

 

predicates

 

   member(number, number_list)

   member(person, person_list)

 

goal

   member(3,[1,2,3,4,5]), write(” нашли 3 ”),

   member(john, [tom, bob, jerry, john],

   write(” нашли Джона ”).

 

clauses

 

   member(Head, [Head|_]).

   member(Head, [_|Tail]) :-

          member(Head, Tail).

/*     Конец программы          */

На экране появится True и печать двух сообщений.

Упражнение 6.2.

Задайте следующую внешнюю цель:

member(44,[11,44,11,33,44,44,55])

В скольких случаях будет достигнут успех?

8. ПРИСОЕДИНЕНИЕ СПИСКА

Слияние двух списков в третий принадлежит к числу наиболее полезных при работе со списками операций. Этот процесс обычно называют присоединением одного списка к другому.

В качестве примера рассмотрим две переменные,L1 и L2, представляющие списки. Переменные имеют значения [1,2,3] и [4,5]. Назовем их входными списками. Предикат, присоединящий L2 к L1 и создающий выходной список L3, назовем concat.

Весь процесс можно представить себе в виде такой совокупности действий:

1. Список L3 вначале пуст.

2. Элементы  списка L1 пересылаются в L3, теперь значением L3 будет [1,2,3].

3. Элементы  списка L2 пересылаются в L3, в результате чего тот принимает значение [1,2,3,4,5].

Структура правила для выполнения этих действий достаточна проста:

concat([],L,L).

concat([N|L1],L2,[N|L3]) :-

   concat(L1,L2,L3).

Поясним теперь, как будет функционировать это правило, если на вход подать списки L1=[1,2,3] и L2=[4,5]. Сначала Турбо-Пролог пытается удовлетворить первый вариант правила: concat([],L,L). Для того чтобы удовлетворить это правило, первый объект предиката concat нужно сделать пустым списком. Вначале же предикат concat имеет форму

concat([1,2,3],[4,5],L3)

Отметим, что третий, выходной список в этой форме пока еще не определен. Внутренний процесс унификации Турбо-Пролога, пытаясь удовлетворить второе правило concat, раскручивает цепочку рекурсий до тех пор, пока не обнуляет первый список.

ЭЛЕМЕНТЫ ПЕРВОГО СПИСКА ПРИ ЭТОМ ПОСЛЕДОВАТЕЛЬНО ПЕРЕСЫЛАЮТСЯ В СТЕК. Стек, логическая структура данных в памяти компьютера, обеспечивает временное хранение этих элементов.

Когда первый объект предиката concat окажется пустым списком, становится возможным применение первого варианта правила. Третий список при этом означивается вторым.

Такой процесс можно пояснить при помощи двух состояний concat, до и после применения первого варианта правила:

concat([],[4,5],_)

concat([],[4,5],[4,5])

В данный момент процедуры унификации Турбо-Пролога полностью удовлетворили это правило, и Турбо-Пролог начинает сворачивать рекурсивные вызовы второго правила:

concat([N|L1], L2, [N|L3]) :-

   concat(L1,L2,L3).

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

Следует особо отметить, что элементы излекаются в обратном порядке (это стек!), и что значение извлеченного из стека элемента присваивается переменной N одновременно в [N|L1] и [N|L3]. Шаги данного процесса можно представить так:

concat([],[4,5],[4,5])

concat([3],[4,5],[3,4,5])

concat([2,3],[4,5],[2,3,4,5])

concat([1,2,3],[4,5],[1,2,3,4,5])

Присвоение элементов стека происходит рекурсивно до тех пор, пока стек не будет пуст. В результате список L3 будет содержать элеметы обоих входных списков — [1,2,3,4,5].

Программа 6.4 «Присоединение списка» демонстрирует применение данного метода. Внешней целью для программы может служить ранее разобранный пример:

concat([1,2,3],[4,5],L)

/* Программа 6.4 «Присоединение списка».      */

/* Назначение:  слияние двух списков.         */

domains

 

   list = integer *

 

predicates

 

   concat(list,list,list)

 

clauses

 

   concat([],L,L).

   concat([N|L1], L2, [N|L3]) :-

                  concat(L1,L2,L3).

/*    Конец программы            */

9. ДОБАВЛЕНИЕ И УДАЛЕНИЕ ЭЛЕМЕНТА

Рассмотрим случай, когда элемент X добавляется к началу списка L:

add(X,L,[X|L])

Случай, когда элемент добавляется к концу списка, можно описать аналогично правилу conc:

вначале рассмотреть добавление X к пустому списку;

если список не пуст, то его элементы временно пересылаются в стек, а затем поочередно добавляются к голове списка [X].

Можно воспользоваться процедурой conc:

add_end(X, L, L1):-

   conc(L, X, L1).

Удаление заданного элемента X из списка L описывается следующей недетерминированной процедурой:

del(X, [X|T], T).

del(X, [H|T], [H|T1]):-

   del(X, T, T1).

Первое правило соответствует случаю, когда X совпадает с головой списка, второе — вызывает рекурсию для поиска X в хвосте. При возвратах будет удаляться каждый раз новое вхождение X. На внешний запрос del(2, [2,3,2,1]) система ответит

L=[3,2,1]

L=[2,3,1]

Упражнение 6.3.

1. Напишите  процедуру удаления элемента  из конца списка без использования процедуры conc.

2. Напишите  процедуру удаления ВСЕХ вхождений элемента.

10. ПОДСПИСОК

Составим процедуру, определяющую, является ли список S подсписком списка L:

sublist(S, L)

Будем считать, что список L состоит из трех списков L1, S, L3, а списки S и L3 составляют список L2 (рис. 6.2).

рис. 6.2

Отметим, что списки L1, S, L3 могут быть пустыми. Исходя из наглядных геометрических соображений, запишем правило принадлежности списка S списку L:

sublist(S, L):-

   conc(L1, L2, L),

   conc(S, L3, L2).

Это правило имеет чисто декларативный смысл. В нем утверждается, что если список L состоит из списков L1 и L2, и список L2 состоит из списков S и L3, то S есть подсписок L.

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

Упражнение 6.4.

Сгенерировать все подсписки списка [1,2,3], подавляя печать пустого списка [].

11. ПЕРЕСТАНОВКИ СПИСКА

Составим процедуру, генерирующую всевозможные перестановки P заданного списка L:

perest(L, P)

Весь процесс можно представить себе в виде такой совокупности действий:

1. Отсекаем  от списка голову H.

2. Переставляем  хвост.

3. Вносим H в произвольное место переставленного хвоста.

Граничным условием рекурсии будет перестановка пустого списка:

perest([],[]).

Рекурсивное правило:

perest([X|T]):-

   perest(T, T1),

   into(X, T1, P).

Недетерминированная процедура вставки элемента в произвольное место списка выглядит так:

/* или X становится головой списка, или  элементом 
   хвоста */

into(X, L, [X|L]).

into(X, [H|T], [H|T1]):-

   into(X, T, T1).

Упражнение 6.5.

Соберите в одну программу все рассмотренные нами правила работы со списками применительно к спискам из целых чисел.

ГЛАВА 7. СОРТИРОВКА СПИСКОВ

1. РАЗДЕЛЕНИЕ СПИСКА НА ДВА

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

Рассмотрим предикат div1, аргументами которого являются элемент данных и три списка:

div1(Middle,L,L1,L2)

Элемент Middle здесь является разделителем, L — это исходный список, а L1 и L2 — подсписки, получающиеся в результате деления списка L. Если элемент исходного списка меньше или равен Middle, то он помещается в список L1; если больше, то в список L2.

Предположим, что вначале значением переменной Middle является число 40, переменной L присвоен список [30,50,20,25,65,95], а переменные L1 и L2 свободные.

div1(40,[30,50,20,25,65,95],L1,L2)

Идея разделения следующая:

1. Извлекаем  из списка голову H, а потом сравнивается с элементом Middle.

2. Если  значение H меньше или равно значению Middle, то элемент помещается в список L1, в противном случае — в список L2.

3. Повторяем  эту последовательность действий  для хвоста.

В результате применения правила к списку [30,50,20,25,65,95] значениями списков L1 и L2 станут соответственно [30,20,25] и [50,65,95].

Само правило для разделения списка записывается следующим образом:

div1(_,[],[],[]):-!.

div1(Middle,[H|T],[H|T1],L2) :-

   H <= Middle,!,

   div1(Middle,T,T1,L2).

 

div1(Middle,[H|T],L1,[H|T2]) :-

   div1(Middle,T,L1,T2).

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

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

/* Программа 7.1 «Деление списка».        */

/* Назначение: Разделение списка на два.   */

domains

   list = integer *

 

predicates

   div1(integer,list,list,list)

 

clauses

 

   div1(_,[],[],[]):-!.

   div1(Middle,[H|T],[H|T1],L2) :-

      H <= Middle,

      div1(Middle,T,T1,L2).

 

   div1(Middle,[H|T],L1,[H|T2]) :-

                 div1(Middle,T,L1,T2).

/*          Конец программы          */

2. СОРТИРОВКА СПИСКОВ МЕТОДОМ ВСТАВКИ

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

Существует много способов сортировки списков. Сортирующее правило Турбо-Пролога принимает на вход неотсортированный список, и выдает отсортированный на выходе. Входной список называется ИСХОДНЫМ, выходной — ЦЕЛЕВЫМ.

Метод вставки особенно удобен для реализации его на Турбо-Прологе.

Идея этой сортировки следующая:

1. Извлекаем  из списка голову H.

2. Методом  вставки сортируем хвост.

3. Вносим H в подходящее место отсортированного хвоста.

Опишем предикат, производящий сортировку списка методом вставки

insert_sort(Source_list,Target_list)

Внешней целью в задаче сортировки списка [4,7,3,9] будет утверждение

insert_sort([4,7,3,9],S)

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

insert_sort([],[]).

insert_sort([H|T],Sorted_list) :-

   insert_sort(T,Sorted_Tail),

   insert(H,Sorted_Tail,Sorted_list).

insert(X,[H|Sorted_list],[H|Sorted_list1]) :-

   X > H,!,

   insert(X,Sorted_list,Sorted_list1).

insert(X,Sorted_list,[X|Sorted_list]).

Дальнейшее обсуждение продемонстрирует работу правил на примере списка [4,7,3,9].

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

insert_sort([4,7,3,9],_)

Первая попытка удовлетворить правило insert_sort осуществляется с первым вариантом правила

insert_sort([],[])

Для удовлетворения правила оба списка должны быть пустыми.

Согласно второму варианту правила внутренние унификационные процедуры Турбо-Пролога пытаются сделать пустым исходный список. Рекурсия убирает элементы исходного списка, начиная с головы, и переносит их в стек. В результате применения этой процедуры список становится нулевым. Теперь первый вариант правила insert_sort производит обнуление выходного списка.

Далее, первое взятое из стека значение (9), вносится во второй список:

insert(9,[],[9])

Из стека извлекается следующий элемент (3), и при помощи второго варианта insert вставляется в выходной список слева от 9:

insert(3,[9],[3,9])

Происходит возврат к insert_sort, теперь оно имеет форму

insert_sort([3,9],[3,9])

Таким образом, все элементы извлекаются из стека и помещаются в выходной список.

/* Программа 7.2. Назначение:              */

/* демонстрация  сортировки списка          */

/* в  порядке возрастания методом вставки   */

domains

   list = integer *

 

predicates

 

   insert_sort(list,list)

   insert(integer,list,list)

 

clauses

 

   insert_sort([],[]).

   insert_sort([H|T,Sorted_list) :-

      insert_sort(T,Sorted_Tail),

insert(H,Sorted_Tail,Sorted_list).

   insert(X,[H|Sorted_list],[H|Sorted_list1]) :-

X > H, !,

insert(X,Sorted_list,Sorted_list1).

   insert(X,Sorted_list,[X|Sorted_list]).

/*       Конец программы              */

3. БЫСТРАЯ СОРТИРОВКА

Идея быстрой сортировки следующая:

1. Убрать  голову H.

2. С помощью  процедуры div1 разбить список на два:

— меньший либо равный H (Small)

— больший H (Big)

3. Методом  быстрой сортировки отсортировать  списки Small и Big.

4. Соединить  списки Small_sort и [H|Big_sort] с помощью процедуры conc.

Опишем предикат, производящий сортировку списка методом быстрой сортировки:

supersort(list,list)

Правила, реализующие этот способ сортировки, имеют следующую структуру:

supersort([],[]).

supersort([H|T],Sorted_list) :-   

   div1(H,T, Small,Big),

   supersort(Small,Small_sort),

   supersort(Big,Big_sort),

   conc(Small_sort,[H|Big_sort],Sorted_list).

Процедуры conc и div1 уже были описаны ранее.

4. БЫСТРАЯ СОРТИРОВКА_1

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

Итак, необходимо:

1. Разбить L на два списка L1 и L2 примерно одинаковой длины.

2. Отсортировать их, получив списки S1 и S2.

3. Слить отсортированные S1 и S2, получив отсортированный список S.

Рекурсивное правило сортировки supersort1 будет выглядеть так:

supersort1(L,S):-

   % разделение на два равных  списка

   div2(L,L1,L2),

   supersort1(L1,S1),

   supersort1(L2,S2),

   % соединение отсортированных списков

   concsort (S1,S2,S).

Определим, что в этой сортировке будет являться граничным условием, то есть задачей, решаемой непосредственно. Список [X], состоящий из одного элемента, правило div2 разделит на два: пустой [] и одноэлементный [X].

Следовательно, у нашей сортировки будут два граничных условия:

supersort1([],[]).

supersort1([X],[X]).

Опишем процедуру div2.

Идея очень простая:

1. Первый элемент списка [X,Y|T] отправляется в список L1, второй — в список L2.

2. Вызывается div2 для хвоста T.

div2([],[],[]).

div2([X],[X],[]).

div2([X,Y|L],[X|L1],[Y|L2]):-

    div2(L,L1,L2).

Остается описать процедуру concsort(S1,S2,S) слияния двух отсортированных списков S1 и S2 в отсортированный список S.