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) используются в качестве краткой записи для этого «чего-либо», и, таким образом, тип функции будет следующим:

general_insert_element: (('t x 't) -> bool) -> 't -> 't list

где типовые переменные записаны в языке ML как идентификаторы с пред­шествующим

апострофом

Использование функций более высокого порядка, т. е. функций, аргумента­ми которых являются функции, не ограничено такими статическими конст­рукциями, как обобщения. Чрезвычайно полезная функция — тар:

fun map f [] = [ ]

| mар f head :: tail = (f head):: (map f tail)

Эта функция применяет первый аргумент к списку значений, производя спи­сок результатов. Например:

map even [1, 3, 5, 2, 4, 6] = [false, false, false, true, true, true]

map min [(1,5), (4,2), (8,1)] = [1,2,1]

Этого фактически невозможно достичь в процедурных языках; самое боль­шее, мы могли бы написать подпрограмму, которая получает указатель на функцию в качестве аргумента, но мы потребовали бы разных подпрограмм для каждой допустимой сигнатуры аргумента функции.

Обратите внимание, что эта конструкция надежная. Тип тар следующий:

mар: (t1 -> t2) -> 't1 list -> t2 list

Это означает, что элементы списка аргументов t1 list все должны быть совме­стимы с аргументом функции t1, а список результата t2 list будет состоять только из элементов, имеющих тип результата функции t2.

Функции более высокого порядка абстрагируются от большинства управ­ляющих структур, которые необходимы в процедурных языках. В другом при­мере функция accumulate реализует «составное» применение функции, а не создает список результатов, подобно mар:

fun accumulate f initial [] = initial

| accumulate f initial head::tail - accumulate f (f initial head) tail

Функция accumulate может использоваться для создания ряда полезных фун­кций. Функции

fun minlist = accumulate min maxint

fun sumlist = accumulate "+" 0

вычисляют минимальное значение целочисленного списка и сумму целочис­ленного списка соответственно. Например:

minlist [3, 1,2] =

accumulate min maxint [3, 1,2] =

accumulate min (min maxint 3) [1,2] =

accumulate min 3 [1, 2] =

accumulate min (min 3 1) [2] =

accumulate min 1 [2] =

accumulate min (min 1 2) [] =

accumulate min 1 [] =

1

Функции более высокого порядка не ограничиваются списками; можно на­писать функции, которые обходят деревья и применяют функцию в каждом узле. Кроме того, функции могут быть определены на типовых переменных так, чтобы их можно было использовать без изменений при определении но­вых типов данных.