В языке ML вам не
В языке ML вам не нужно объявлять тип функции; компилятор автоматически выводит тип функции из типов аргументов и типа результата. Если компилятор не может вывести тип, вам придется задать нужное количество объявлений типа, чтобы ликвидировать неопределенность выражения. Контроль соответствия типов статический, поэтому, когда функция применяется к значению, проверка соответствия типа функции типу параметра делается во время компиляции.
Обратите внимание, что эта функция рекурсивная. Рекурсия чрезвычайно важна в функциональных языках программирования; при отсутствии «операторов» это единственный способ создания циклов при вычислении выражения.
В качестве заключительного примера покажем, как на языке ML написать алгоритм сортировки вставкой (insertion sort). Вы используете этот алгоритм для сортировки при игре в карты: по очереди берете карты из колоды и кладете их в нужное место:
fun insertion_sort [] = []
| insertion_sort head:: tail =
insert_element head insertion_sort tail
and
fun insert_element x [] = [x]
| insert_element x head:: tail =
if x < head then x::head:: tail
else head:: (insert_element x tail)
Эти функции имеют типы:
insertion_sort: int list -> int list
insert_element: int -> int list -> int list
Как только вы привыкнете к этой записи, читать такие программы будет просто:
Отсортированный пустой список является пустым. При сортировке непустого списка берется первый элемент х, сортируется оставшаяся часть списка tail, а затем х вставляется в подходящее место отсортированного списка.
Элемент х вставляется в пустой список, создавая список из одного элемента. Чтобы вставить х в непустой список, нужно сравнить х с первым элементом (head) списка: 1) если х меньше head, сделать х новым первым элементом списка; 2) в противном случае создать новый список, составленный из head, за которым следует остаток списка, в который вставлен х.
