Демонстрация сортировки списка при помощи вставок для целочисленных списков.

/* 5.6.2013
Среда - EZY Prolog
Программа «Сортировка списков» реализует правило сортировки в ПОРЯДКЕ ВОЗРАСТАНИЯ при помощи вставок для целочисленных списков. */
 
domains
/* домен списков, состоящие из целых чисел */
number = integer
list = number *
 
predicates
insert_sort(list,list)
insert(number,list,list)
asc_order(number,number)
 
clauses
/* Вначале Пролог применяет приведенные правила к исходному списку, выходной список в этот момент еше не определен.
Для удовлетворения правила ниже оба списка должны быть пустыми. */
insert_sort([],[]).
 
/* Правило ниже трактует список как комбинацию головы списка и его хвоста.
Внутренние унификационные процедуры Пролога пытаются сделать пустым исходный список.
Устранение элементов списка начинается с головы списка и осуществляется рекурсивно.
Часть правила, которая производит удаление элементов - insert_sort([X|Tail],Sorted_list) :- insert_sort(Tail,Sorted_Tail).
 
По мере того как Пролог пытается удовлетворить первое из правил, происходят рекурсивные вызовы insеrt_sort, 
при этом значениями Х последовательно становятся все элементы исходного списка, которые затем помещаются в стек.
В результате применения этой процедуры список становится нулевым.
 
Теперь первый вариант правила insert_sort производит обнуление выходного списка, и таким образом правилу придается форма
insert_sort([],[]).
 
Далее, после того как удовлетворен первый вариант правила insert_sort, Пролог пытается удовлетворить второе правило из тела insert_sort - правило insert.
 
Переменной Х сначала присваивается первое взятое из стека значение, 9, а правило insert принимает форму insert(9,[],[9]).
Теперь удовлетворено и второе правило из тела insert_sort - правило insert (его второй вариант), поэтому происходит возврат на один круг рекурсии insert_sort.
 
Из стека извлекается следующий элемент, 3, и испытывается первый вариант insert, а значит и правило упорядочивания asc_order(X,Y) :- X>Y.
 
Переменная Х здесь имеет значение 3, Y - значение 9, само правило имеет вид asc_order(3,9) :- 3>9.
 
Так как оно неуспешно (3 меньше 9), то вместе с ним неуспешен и первый вариант insert.
 
При помощи второго варианта insert 3 вставляется в выходной список слева от 9: insert(3,[9],[3,9]).
 
Происходит возврат к insert_sort, теперь оно имеет форму insert_sort([3,9],[3,9]).
 
На следующем круге рекурсии происходит вставка очередного элемента из стека, а именно 7.
 
В начале работы на этом круге правило insert имеет вид insert(7,[3,9],_).
 
Сначала происходит сравнение 7 и 3, asc_order(7,3):- 7>3.
 
Так как данное правило успешно, то элемент 3 убирается в стек, и insert вызывается рекурсивно еще раз, но уже с хвостом списка - [9] : insert(7,[9],_).
 
Так как правило asc_order(7,9):- 7>9 неуспешно, то испытывается второй вариант insert (успешно), происходит возврат на предыдущие круги рекурсии сначала insert, а потом insert_sort.
 
В результате 7 помещается в выходной список между элементами 3 и 9. insert(7,[3,9],[3,7,9]).
 
При возврате еще на один круг рекурсии insert_sort из стека извлекается элемент 4.
 
Правило insert выглядит как insert(4,[3,7,9],_)
 
Далее имеем: правило asc_order(4,3) :- 4>3 успешно, следовательно, следует попытка insert(4,[7,9],_).
 
Правило же asc_order(4,7) :- 4>7. неуспешно.
 
Нетрудно сообразить теперь, что 4 окажется в выходном списке между 3 и 7 : insert(4,[3,7,9],[3,4,7,9]).
 
insert_sort([4,7,3,9],[3,4,7,9]).
 
Теперь в стеке больше нет элементов, и все рекурсии insert_sort уже свернуты.
 
Выходной список получил при этом значение [3,4,7,9], удовлетворена цель программы.
 
*/
 
insert_sort([X|Tail],Sorted_list) :- insert_sort(Tail,Sorted_Tail), write ("X = ", X, " Tail = ", Tail, " Sorted_Tail = ", Sorted_Tail), nl,  insert(X,Sorted_Tail,Sorted_list), write ("X = ", X, " Tail = ", Tail, " Sorted_list = ", Sorted_list), nl. 
 
insert(X,[Y|Sorted_list],[Y|Sorted_list1]) :- asc_order(X,Y), !, insert(X,Sorted_list,Sorted_list1).
 
insert(X,Sorted_list,[X|Sorted_list]).
 
/* Сортировка по возрастанию */
asc_order(X,Y) :- X>Y.
 
/* Сортировка по убыванию
asc_order(X,Y) :- X<Y.  */
 
goal
/* Внешние цели -
insert_sort([4,7,3,9],S).*/

Результат:
S=3,4,7,9

!!Рекомендуем: Что должен знать современный человек? ⇒ Семейная Энциклопедия Здоровья ⇒ Самоанализ. Работа над собой ⇒ Оглавление ⇒ Главная сайта