в другую функцию, которая отображает
Обратите внимание, что -> имеет правую ассоциативность:
insert_element: int -> (int list -> int list)
Функция отображает целое число в другую функцию, которая отображает список целых в список целых. При помощи частичных вычислений мы можем создавать новые функции подобно следующей:
fun insert_4 = insert_element 4
которая вставляет 4 в список целых.
В отличие от процедурной программы для того же самого алгоритма здесь нет никаких индексов и никаких for-циклов. Кроме того, ее можно легко обобщить для сортировки объектов других типов, просто заменяя операцию «<» соответствующей булевой функцией для сравнения двух значений рассматриваемого типа. Чтобы создать список, явные указатели не нужны; они заданы неявно в представлении данных. Конечно, сортировка списков в любом языке не так эффективна, как сортировка массива «на своем месте», но для многих приложений, использующих списки, вполне практична.
Определение новых типов
Повсюду в этой книге мы видели, что определение новых типов весьма существенно, если язык программирования должен моделировать реальные объекты. Современные функциональные языки программирования также имеют эту возможность. Определим (рекурсивный) тип для деревьев, узлы которых помечены целыми числами:
datatype int tree =
Empty
| T of (int tree x int x int tree)
Это следует читать так:
int tree является новым типом данных, значения которого: 1) новое константное значение Empty (пусто) или 2) значение, которое сформировано конструктором Т, примененным к тройке, состоящей из дерева, целого числа и другого дерева.
Определив новый тип, мы можем написать функции, которые обрабатывают дерево.
Например:
fun sumtree Empty = О
| sumtree T(left, value, right) =
(sumtree left) + value + (sumtree right)
суммирует значения, помечающие узлы дерева, и:
