TURBO PROLOG. Терёхин В.В. - 114 стр.

      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], удовле-
творена цель программы.
      Программа "Сортировка списка" (листинг 5.6) реализует правило сор-
тировки при помощи вставок для целочисленных списков. Программа ра-
ботает в интерактивном режиме.
____________________________________________________________
             Листинг 5.6
/* Программа: Coртировка списка                          */
/* Назначение: Сортировка списка целых чисел.           */
/*         в порядке возрастания при помощи            */
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),
                                     insert(X,Sorted_Tail,Sorted_list).


                                                                          114