В математике и информатике функция высшего порядка ( HOF ) — это функция , которая выполняет по крайней мере одно из следующих действий:
Все остальные функции являются функциями первого порядка . В математике функции высшего порядка также называются операторами или функционалами . Дифференциальный оператор в исчислении является распространенным примером, поскольку он отображает функцию в ее производную , также являющуюся функцией. Функции высшего порядка не следует путать с другими использованиями слова «функтор» в математике, см. Функтор (значения) .
В нетипизированном лямбда-исчислении все функции являются функциями высшего порядка; в типизированном лямбда-исчислении , из которого выведено большинство функциональных языков программирования, функции высшего порядка, которые принимают одну функцию в качестве аргумента, являются значениями с типами вида .
mapФункция, встречающаяся во многих функциональных языках программирования, является одним из примеров функции высшего порядка. Она принимает в качестве аргументов функцию f и коллекцию элементов, а в качестве результата возвращает новую коллекцию, в которой f применяется к каждому элементу из коллекции.qsortПримеры не предназначены для сравнения и противопоставления языков программирования, а служат примерами синтаксиса функций высшего порядка.
В следующих примерах функция высшего порядка twiceберет функцию и применяет ее к некоторому значению дважды. Если twiceее нужно применить несколько раз для одного и того же, fто желательно вернуть функцию, а не значение. Это соответствует принципу « не повторяйся ».
дважды ← { ⍺⍺ ⍺⍺ ⍵ } плюстри ← { ⍵ + 3 } g ← { плюстри дважды ⍵ } g 7 13 Или молчаливо:
дважды ← ⍣ 2 плюстри ← + ∘ 3 g ← плюстри дважды g 7 13 Использование std::functionв C++11 :
#include <iostream> #include <function> auto дважды = []( const std :: function < int ( int ) >& f ) { return [ f ]( int x ) { return f ( f ( x )); }; }; auto plus_three = []( int i ) { return i + 3 ; }; int main () { auto g = twice ( plus_three ); std :: cout << g ( 7 ) << '\n' ; // 13 } Или с помощью универсальных лямбда-выражений, предоставляемых C++14:
#include <iostream> auto дважды = []( const auto & f ) { return [ f ]( int x ) { return f ( f ( x )); }; }; auto plus_three = []( int i ) { return i + 3 ; }; int main () { auto g = twice ( plus_three ); std :: cout << g ( 7 ) << '\n' ; // 13 } Используя только делегаты:
с использованием Системы ; public class Program { public static void Main ( string [] args ) { Func < Func < int , int > , Func < int , int >> twice = f => x => f ( f ( x )); Func < int , int > plusThree = i => i + 3 ; var g = дважды ( plusThree ); Консоль.WriteLine ( g ( 7 )) ; // 13 } } Или, что эквивалентно, со статическими методами:
с использованием Системы ; открытый класс Программа { частный статический Func < int , int > Дважды ( Func < int , int > f ) { return x => f ( f ( x )); } частный статический int PlusThree ( int i ) => i + 3 ; public static void Main ( string [] args ) { var g = Twice ( PlusThree ); Консоль.WriteLine ( g ( 7 )) ; // 13 } } ( defn дважды [ f ] ( fn [ x ] ( f ( f x )))) ( defn плюс-три [ i ] ( + i 3 )) ( def g ( дважды плюс-три )) ( println ( g 7 )) ; 13 дважды = функция ( f ) { вернуть функцию ( x ) { вернуть f ( f ( x )); }; };plusThree = функция ( i ) { return i + 3 ; };г = дважды ( плюсТри );writeOutput ( g ( 7 )); // 13( defun twice ( f ) ( lambda ( x ) ( funcall f ( funcall f x )))) ( defun plus-three ( i ) ( + i 3 )) ( defvar g ( twice #' plus-three )) ( print ( funcall g 7 )) импорт std.stdio : writeln ; псевдоним дважды = ( f ) => ( int x ) => f ( f ( x )); псевдоним plusThree = ( int i ) => i + 3 ; void main () { auto g = twice ( plusThree ); writeln ( g ( 7 )); // 13 } Функция int ( int ) дважды ( Функция int ( int ) f ) { return ( x ) { return f ( f ( x )); }; } int plusThree ( int i ) { return i + 3 ; } void main () { final g = twice ( plusThree ); print ( g ( 7 )); // 13 } В Elixir можно смешивать определения модулей и анонимные функции.
defmodule Hof do def twice ( f ) do fn ( x ) -> f . ( f . ( x )) конец конец конец plus_three = fn ( i ) -> i + 3 конец г = Хоф . дважды ( плюс_три ) IO . ставит г . ( 7 ) # 13 В качестве альтернативы мы также можем составить композицию, используя чисто анонимные функции.
дважды = fn ( f ) -> fn ( x ) -> f . ( f . ( x )) конец конец plus_three = fn ( i ) -> i + 3 конец г = дважды . ( плюс_три ) IO . ставит г . ( 7 ) # 13 или_иначе ([], _) -> ложь ; или_иначе ([ F | Fs ], X ) -> или_иначе ( Fs , X , F ( X )). или_иначе ( Fs , X , false ) -> или_иначе ( Fs , X ); или_иначе ( Fs , _, { false , Y } ) -> или_иначе ( Fs , Y ); или_иначе (_, _, R ) -> R. или_иначе ([ fun erlang : is_integer / 1 , fun erlang : is_atom / 1 , fun erlang : is_list / 1 ] , 3.23 ) . В этом примере Erlang функция высшего порядка or_else/2принимает список функций ( Fs) и аргумент ( X). Она вычисляет функцию Fс аргументом Xв качестве аргумента. Если функция возвращает false, то будет вычислена Fследующая функция в . Если функция возвращает false , то будет вычислена следующая функция в с аргументом . Если функция возвращает , то функция высшего порядка вернет . Обратите внимание, что , , и могут быть функциями. Пример возвращает .FsF{false, Y}FsYFRor_else/2RXYRfalse
пусть дважды f = f >> f пусть плюс_три = (+) 3 пусть g = дважды плюс_три г 7 |> printf "%A" // 13 основной пакет импорт "фмт" func дважды ( f func ( int ) int ) func ( int ) int { return func ( x int ) int { return f ( f ( x )) } } func main () { plusThree := func ( i int ) int { return i + 3 } g := дважды ( плюсТри ) fmt.Println ( g ( 7 ) ) // 13 } Обратите внимание, что функциональный литерал может быть определен либо с помощью идентификатора ( twice), либо анонимно (назначен переменной plusThree).
def twice = { f , x -> f ( f ( x )) } def plusThree = { it + 3 } def g = twice . curry ( plusThree ) println g ( 7 ) // 13 дважды :: ( Int -> Int ) -> ( Int -> Int ) дважды f = f . f plusThree :: Целое -> Целое plusThree = ( + 3 ) main :: IO () main = print ( g 7 ) -- 13 где g = дважды плюсТри Явно,
дважды =. наречие : 'uu y' plusthree =. глагол : 'y + 3' g =. plusthree дважды g 7 13 или молчаливо,
дважды =. ^: 2 плюстри =. +& 3 г =. плюстри дважды г 7 13 Использование только функциональных интерфейсов:
импорт java.util.function.* ; class Main { public static void main ( String [] args ) { Function < IntUnaryOperator , IntUnaryOperator > twice = f -> f .andThen ( f ) ; IntUnaryOperator plusThree = i -> i + 3 ; var g = дважды . применить ( plusThree ); System.out.println ( g.applyAsInt ( 7 ) ) ; // 13 } } Или, что эквивалентно, со статическими методами:
импорт java.util.function.* ; class Main { private static IntUnaryOperator twice ( IntUnaryOperator f ) { return f . andThen ( f ); } частный статический int plusThree ( int i ) { return i + 3 ; } public static void main ( String [] args ) { var g = twice ( Main :: plusThree ); System.out.println ( g.applyAsInt ( 7 ) ) ; // 13 } } Со стрелочными функциями:
"использовать строго" ;константа дважды = f => x => f ( f ( x )); const plusThree = i => i + 3 ; const g = дважды ( plusThree ); консоль.журнал ( г ( 7 )) ; // 13 Или с классическим синтаксисом:
"использовать строго" ;функция дважды ( f ) { return function ( x ) { return f ( f ( x )); }; } функция plusThree ( i ) { return i + 3 ; } const g = дважды ( plusThree ); консоль.журнал ( г ( 7 )) ; // 13 julia> функция дважды ( f ) функция результат ( x ) вернуть f ( f ( x )) конец вернуть результат конец дважды (общая функция с 1 методом) julia> plusthree ( i ) = i + 3 plusthree (общая функция с 1 методом) julia> g = twice ( plusthree ) (::var"#result#3"{typeof(plusthree)}) (универсальная функция с 1 методом) джулия> г ( 7 ) 13 весело дважды ( f : ( Int ) -> Int ): ( Int ) -> Int { return { f ( f ( it )) } } веселье плюсТри ( i : Int ) = i + 3 fun main () { val g = дважды ( :: plusThree ) println ( g ( 7 )) // 13 } функция дважды ( f ) возвращает функцию ( x ) возвращает f ( f ( x )) конец конецфункция plusThree ( i ) возвращает i + 3 конецлокальный g = дважды ( плюсТри )печать ( г ( 7 )) -- 13функция результат = дважды ( f ) результат = @( x ) f ( f ( x )); конец плюстри = @( i ) i + 3 ; г = дважды ( плюстри ) дисп ( г ( 7 )); % 13 пусть дважды f x = f ( f x )пусть плюс_три = (+) 3пусть () = пусть g = дважды плюс_три в print_int ( g 7 ); (* 13 *) print_newline ()<?phpобъявить ( strict_types = 1 );функция дважды ( вызывается $f ) : Закрытие { return function ( int $x ) use ( $f ) : int { return $f ( $f ( $x )); }; }функция plusThree ( int $i ) : int { return $i + 3 ; }$g = дважды ( 'плюсТри' );эхо $g ( 7 ), " \n " ; // 13или со всеми функциями в переменных:
<?phpобъявить ( strict_types = 1 );$twice = fn ( вызываемый $f ) : Замыкание => fn ( int $x ) : int => $f ( $f ( $x ));$plusThree = fn ( int $i ) : int => $i + 3 ;$g = $twice ( $plusThree );эхо $g ( 7 ), " \n " ; // 13Обратите внимание, что стрелочные функции неявно захватывают любые переменные, которые поступают из родительской области видимости, [1] тогда как анонимным функциям useдля того же требуется ключевое слово.
использовать строгий ; использовать предупреждения ; подставить дважды { мой ( $f ) = @_ ; подставить { $f -> ( $f -> ( @_ )); }; } подплюсТри { мой ( $i ) = @_ ; $ i + 3 ; } мой $g = дважды ( \& плюсТри ); распечатать $g -> ( 7 ), "\n" ; # 13 или со всеми функциями в переменных:
использовать строгий ; использовать предупреждения ; мой $twice = sub { мой ( $f ) = @_ ; sub { $f -> ( $f -> ( @_ )); }; }; мой $plusThree = sub { мой ( $i ) = @_ ; $i + 3 ; }; мой $g = $twice -> ( $plusThree ); распечатать $g -> ( 7 ), "\n" ; # 13 >>> def twice ( f ): ... def result ( x ): ... return f ( f ( x )) ... return result>>> plus_three = лямбда i : i + 3>>> г = дважды ( плюс_три ) >>> г ( 7 ) 13 Синтаксис декоратора Python часто используется для замены функции результатом передачи этой функции через функцию более высокого порядка. Например, функция gможет быть реализована эквивалентно:
>>> @twice ... def g ( i ): ... return i + 3>>> г ( 7 ) 13дважды <- \ ( f ) \ ( x ) f ( f ( x )) plusThree <- функция ( i ) i + 3 г <- дважды ( плюсТри ) > г ( 7 ) [ 1 ] 13 sub дважды ( Вызываемый:D $f ) { return sub { $f ( $f ( $^x )) };}sub plusThree ( Int:D $i ) { return $i + 3 ;}мой $g = дважды ( &plusThree );скажем $g ( 7 ); # 13В Raku все объекты кода являются замыканиями и, следовательно, могут ссылаться на внутренние «лексические» переменные из внешней области видимости, поскольку лексическая переменная «закрыта» внутри функции. Raku также поддерживает синтаксис «pointy block» для лямбда-выражений, которые могут быть назначены переменной или вызваны анонимно.
def дважды ( f ) -> ( x ) { f . call ( f . call ( x )) } конец плюс_три = -> ( я ) { я + 3 } г = дважды ( плюс_три ) ставит г. колл ( 7 ) # 13 fn дважды ( f : импл Fn ( i32 ) -> i32 ) -> импл Fn ( i32 ) -> i32 { ход | x | f ( f ( x )) } fn plus_three ( i : i32 ) -> i32 { i + 3 } fn main () { пусть g = дважды ( plus_three ); println! ( "{}" , g ( 7 )) // 13 } объект Main { def twice ( f : Int => Int ): Int => Int = f compose f def plusThree ( i : Int ): Int = i + 3 def main ( args : Array [ String ]): Unit = { val g = twice ( plusThree ) печать ( г ( 7 )) // 13 } } ( определить ( составить f g ) ( лямбда ( x ) ( f ( g x )))) ( определить ( дважды f ) ( составить f f )) ( определить ( плюс три i ) ( + i 3 )) ( определить g ( дважды плюс три )) ( дисплей ( g 7 )) ; 13 ( дисплей " \n " ) func дважды ( _ f : @ escaping ( Int ) -> Int ) -> ( Int ) -> Int { return { f ( f ( $0 )) } }пусть плюсТри = { $0 + 3 }пусть g = дважды ( плюсТри )печать ( г ( 7 )) // 13установить дважды {{ f x } {применить $f [применить $f $x ]}} установить plusThree {{ i } {вернуть [expr $i + 3 ]}} # результат: 13 пут [apply $twice $plusThree 7 ] Tcl использует команду apply для применения анонимной функции (начиная с версии 8.6).
Стандарт XACML определяет функции высшего порядка для применения функции к нескольким значениям наборов атрибутов.
правило allowEntry { разрешающее условие anyOfAny(функция [ stringEqual ], гражданства , разрешенныеГражданства ) } Список функций высшего порядка в XACML можно найти здесь .
объявить функцию локальной: дважды ( $ f , $ x ) { $ f ( $ f ( $ x )) }; объявить функцию local:plusthree ( $ i ) { $ i + 3 }; локальный: дважды ( локальный: плюс три # 1 , 7 ) (: 13 :) Указатели функций в таких языках, как C , C++ , Fortran и Pascal , позволяют программистам передавать ссылки на функции. Следующий код C вычисляет приближение интеграла произвольной функции:
#include <stdio.h> двойной квадрат ( двойной x ) { return x * x ; } двойной куб ( двойной x ) { вернуть x * x * x ; } /* Вычислить интеграл f() в интервале [a,b] */ double integral ( double f ( double x ), double a , double b , int n ) { int i ; double sum = 0 ; double dt = ( b - a ) / n ; for ( i = 0 ; i < n ; ++ i ) { sum += f ( a + ( i + 0.5 ) * dt ); } return sum * dt ; } int main () { printf ( "%g \n " , интеграл ( квадрат , 0 , 1 , 100 )); printf ( "%g \n " , интеграл ( куб , 0 , 1 , 100 )); return 0 ; } Функция qsort из стандартной библиотеки языка C использует указатель на функцию для эмуляции поведения функции высшего порядка.
Макросы также могут использоваться для достижения некоторых эффектов функций более высокого порядка. Однако макросы не могут легко избежать проблемы захвата переменных; они также могут привести к большому количеству дублированного кода, который может быть сложнее оптимизировать компилятору. Макросы, как правило, не являются строго типизированными, хотя они могут производить строго типизированный код.
В других императивных языках программирования можно достичь некоторых из тех же алгоритмических результатов, которые достигаются с помощью функций высшего порядка, путем динамического выполнения кода (иногда называемого операциями Eval или Execute ) в рамках оценки. У этого подхода могут быть существенные недостатки:
В объектно-ориентированных языках программирования, которые не поддерживают функции высшего порядка, объекты могут быть эффективной заменой. Методы объекта действуют по сути как функции, а метод может принимать объекты в качестве параметров и создавать объекты в качестве возвращаемых значений. Однако объекты часто несут дополнительные накладные расходы времени выполнения по сравнению с чистыми функциями, а также добавляют шаблонный код для определения и создания экземпляра объекта и его метода(ов). Языки, которые допускают объекты или структуры на основе стека (в отличие от кучи ), могут обеспечить большую гибкость с этим методом.
Пример использования простой записи на основе стека в Free Pascal с функцией, которая возвращает функцию:
пример программы ; тип int = целое число ; Txy = запись x , y : целое число ; конец ; Tf = функция ( xy : Txy ) : целое число ; функция f ( xy : Txy ) : целое число ; начало Результат : = xy.y + xy.x ; конец ; функция g ( func : Tf ) : Tf ; начало результат := func ; конец ; вар а : Тф ; ху : Txy = ( Икс : 3 ; у : 7 ) ; begin a := g ( @ f ) ; // возвращает функцию "a" writeln ( a ( xy )) ; // печатает 10 end . Функция a()принимает Txyзапись в качестве входных данных и возвращает целочисленное значение суммы полей записи xи y(3 + 7).
Дефункционализацию можно использовать для реализации функций высшего порядка в языках, в которых отсутствуют функции первого класса :
// Дефункционализированные структуры данных функции template < typename T > struct Add { T value ; }; template < typename T > struct DivBy { T value ; }; template < typename F , typename G > struct Composition { F f ; G g ; }; // Дефункционализированные реализации приложений функций template < typename F , typename G , typename X > auto apply ( Composition < F , G > f , X arg ) { return apply ( f . f , apply ( f . g , arg )); } шаблон < имя_типа T , имя_типа X > автоприменить ( Добавить <T> f , X arg ) { return arg + f.value ; } template < typename T , typename X > auto apply ( DivBy <T> f , X arg ) { return arg / f.value ; } // Шаблон функции компоновки высшего порядка < typename F , typename G > Composition < F , G > compose ( F f , G g ) { return Composition < F , G > { f , g }; } int main ( int argc , const char * argv []) { auto f = compose ( DivBy < float > { 2.0f }, Add < int > { 5 }); применить ( f , 3 ); // 4.0f применить ( f , 9 ); // 7.0f вернуть 0 ; } В этом случае разные типы используются для запуска разных функций с помощью перегрузки функций . Перегруженная функция в этом примере имеет сигнатуру auto apply.