с не более чем одним
Например:
permutation([7,2,9,3], [91Tail])
если Tail является перестановкой [7,2,3].
• Список с не более чем одним элементом упорядочен. Список упорядочен, если первые два элемента упорядочены, и список, состоящий из всех элементов, кроме первого, также упорядочен.
С точки зрения процедуры это не самая эффективная программа сортировки; действительно, ее обычно называют медленной сортировкой! Она просто перебирает (генерирует) все перестановки списка чисел, пока не найдет отсортированный список. Однако также просто написать описательную версию более эффективных алгоритмов сортировки типа сортировки вставкой, который мы рассмотрели на языке ML в предыдущей главе:
insertion_sort([], []).
insertion_sort([Head | Tail], List) :-
insertion_sort(Tail, Tail _1),
insert_element(Head, Tail_1, List).
insert_element(X, [], [X]).
insert_element(X, [Head | Tail], [X, Head | Tail]) :-
X=<Head.
insert_element(X, [Head Tail], [Head Tail_1]) :-
insert_element(X, Tail, Tail_1).
С процедурной точки зрения программа вполне эффективна, потому что она выполняет сортировку, непосредственно манипулируя подсписками, избегая бесцельного поиска. Как и в функциональном программировании, здесь нет никаких индексов, циклов и явных указателей, и алгоритм легко обобщается для сортировки других объектов.
Типизация и «неуспех»
В языке Prolog нет статического контроля соответствия типов. К сожалению, реакция машины вывода языка Prolog на ошибки, связанные с типом переменных, может вызывать серьезные затруднения для программиста. Предположим, что мы пишем процедуру для вычисления длины списка:
length([], 0). /* Длина пустого списка равна 0 */
length([Head | Tail], N) : - /* Длина списка равна */
length(Tail, N1), /* длине Tail */
N is N1+1. /* плюс 1*/
и случайно вызываем ее с целочисленным значением вместо списка:
