вычисляет минимальное из всех значений,
fun mintree Empty = maxint
| mintree T(left, value, right) =
min left (min value (mintree right))
вычисляет минимальное из всех значений, помечающих узлы, возвращая наибольшее'целое число maxint для пустого дерева.
Все стандартные алгоритмы обработки деревьев можно написать аналогичным образом: определить новый тип данных, который соответствует древовидной структуре, а затем написать функции для этого типа. При этом никакие явные указатели или циклы не нужны, «работают» только рекурсия и сопоставление с образцом.
16.4. Функции более высокого порядка
В функциональном программировании функция является обычным объектом, имеющим тип, поэтому она может быть аргументом других функций. Например, мы можем создать обобщенную (родовую) форму для insert_element (вставить элемент), просто добавляя функцию compare как дополнительный аргумент:
fun general_insert_element compare x [ ] = [х]
| general_insert_element compare x head:: tail =
if compare x head
then x::head::tail
else head:: (general_insert_element compare x tail)
Если string_compare является функцией от string к boolean:
string_compare: (string x string)—> bool
применение general_insert_element к этому аргументу:
fun string_insert = general_insert_element string_compare
дает функцию следующего типа:
string -> string list -> string list
Обратите внимание, что, в отличие от процедурных языков, это обобщение достигается естественно, без какого-либо дополнительного синтаксиса или семантики, наподобие generic или template.
Но какой тип у general_insert_element? Первый аргумент должен иметь тип «функция от пары чего-либо к булеву значению», второй аргумент должен иметь тип этого самого «чего-либо», а третий параметр является списком этих «чего-либо». Типовые переменные (type variables) используются в качестве краткой записи для этого «чего-либо», и, таким образом, тип функции будет следующим:
