В математике и информатике , функция высшего порядка является функцией , которая делает по крайней мере , одно из следующих действий :
- принимает одну или несколько функций в качестве аргументов (то есть процедурных параметров ),
- в качестве результата возвращает функцию.
Все остальные функции являются функциями первого порядка . В математике функции высшего порядка также называют операторами или функционалами . Дифференциальный оператор в исчислении является типичным примером, так как он отображает функцию его производную , также функция. Функции высшего порядка не следует путать с другим использованием слова «функтор» в математике, см. Функтор (значения) .
В нетипизированном лямбда-исчислении все функции относятся к более высокому порядку; в типизированном лямбда-исчислении , из которого происходит большинство функциональных языков программирования, функции высшего порядка, которые принимают одну функцию в качестве аргумента, являются значениями с типами формы.
Общие примеры
map
Функция, встречающаяся во многих языках функционального программирования, является одним из примеров функции высшего порядка. Он принимает в качестве аргументов функцию f и набор элементов и в результате возвращает новую коллекцию с f, примененным к каждому элементу из коллекции.- Функции сортировки, которые принимают функцию сравнения в качестве параметра, позволяя программисту отделить алгоритм сортировки от сравнений сортируемых элементов. C стандартная функция
qsort
является примером этого. - фильтр
- складывать
- применять
- Состав функций
- Интеграция
- Перезвоните
- Обход дерева
- Грамматика Монтегю , семантическая теория естественного языка, использует функции высшего порядка
Поддержка языков программирования
Прямая поддержка
Примеры не предназначены для сравнения языков программирования, а служат в качестве примеров синтаксиса функций высшего порядка.
В следующих примерах функция высшего порядка twice
принимает функцию и дважды применяет ее к некоторому значению. Если twice
его нужно применить несколько раз для одного и того же, f
предпочтительно, чтобы он возвращал функцию, а не значение. Это соответствует принципу « не повторяйся ».
APL
дважды ← { ⍺⍺ ⍺⍺ ⍵ } plusthree ← { ⍵ + 3 } g ← { плюстри дважды ⍵ } г 7 13
Или молчаливо:
дважды ← ⍣ 2 плюстри ← + ∘ 3 g ← плюстри дважды г 7 13
C ++
Использование std::function
в C ++ 11:
#include #include <функциональный>авто дважды = [] ( const std :: function < int ( int ) > & f ) { return [ & f ] ( int x ) { return f ( f ( x )); }; };auto plus_three = [] ( int я ) { вернуть я + 3 ; };int main () { auto g = дважды ( плюс_три ); std :: cout << g ( 7 ) << '\ n' ; // 13 }
Или с общими лямбдами, предоставляемыми C ++ 14:
#include авто дважды = [] ( const auto & f ) { return [ & f ] ( int x ) { return f ( f ( x )); }; };auto plus_three = [] ( int я ) { вернуть я + 3 ; };int main () { auto g = дважды ( плюс_три ); std :: cout << g ( 7 ) << '\ n' ; // 13 }
C #
Использование только делегатов:
используя Систему ;открытый класс Program { public static void Main ( string [] args ) { Func < Func < int , int >, Func < int , int >> дважды = f => x => f ( f ( x )); Func < int , int > plusThree = i => i + 3 ; var g = дважды ( plusThree ); Консоль . WriteLine ( g ( 7 )); // 13 } }
Или, что то же самое, со статическими методами:
используя Систему ;открытый класс Program { private static Func < int , int > Twice ( 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 } }
Clojure
( defn дважды [ f ] ( fn [ x ] ( f ( f x ))))( Defn plus-three [ i ] ( + i 3 ))( def g ( дважды плюс три ))( println ( g 7 )) ; 13
Язык разметки ColdFusion (CFML)
дважды = функция ( е ) { функция возврата ( х ) { возврат е ( е ( х )); }; }; plusThree = function ( i ) { return i + 3 ; };g = дважды ( plusThree );writeOutput ( g ( 7 )); // 13
D
импорт std . stdio : Writeln ;псевдоним дважды = ( f ) => ( int x ) => f ( f ( x ));псевдоним plusThree = ( int i ) => i + 3 ;void main () { auto g = дважды ( plusThree ); Writeln ( г ( 7 )); // 13 }
Эликсир
В Elixir вы можете смешивать определения модулей и анонимные функции.
defmodule Hof сделать def дважды ( f ) сделать fn ( x ) -> f . ( f . ( x )) конец конец конецplus_three = fn ( i ) -> 3 + i конецg = Hof . дважды ( plus_three )IO . ставит g . ( 7 ) # 13
В качестве альтернативы мы также можем составлять, используя чистые анонимные функции.
дважды = fn ( f ) -> fn ( x ) -> f . ( f . ( x )) конец конецplus_three = fn ( i ) -> 3 + i конецg = дважды . ( плюс_три )IO . ставит g . ( 7 ) # 13
Erlang
or_else ([], _) -> ложь ; or_else ([ F | Fs ], X ) -> or_else ( Fs , X , F ( X )).or_else ( Fs , X , ложь ) -> or_else ( Fs , X ); or_else ( Fs , _, { false , Y }) -> or_else ( Fs , Y ); or_else (_, _, R ) -> R .or_else ([ удовольствие Эрланга : is_integer / 1 , удовольствие Эрланга : is_atom / 1 , удовольствие Эрланга : is_list / 1 ], 3 . 23 ).
В этом примере на Erlang функция высшего порядка or_else/2
принимает список functions ( Fs
) и argument ( X
). Он оценивает функцию F
с аргументом в X
качестве аргумента. Если функция F
возвращает false, Fs
будет оценена следующая функция в . Если функция F
вернется, будет оценена {false, Y}
следующая функция Fs
с аргументом Y
. Если функция F
возвращает R
функция высшего порядка or_else/2
вернутся R
. Обратите внимание, что X
, Y
и R
могут быть функциями. Пример возвращается false
.
F #
пусть дважды f = f >> fпусть plus_three = (+) 3пусть g = дважды плюс_триg 7 |> printf "% A" // 13
Идти
основной пакетимпорт "FMT"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 : = дважды ( plusThree )fmt . Println ( g ( 7 )) // 13 }
Обратите внимание, что функциональный литерал может быть определен либо с идентификатором ( twice
), либо анонимно (назначен переменной plusThree
).
Haskell
дважды :: ( Int -> Int ) -> ( Int -> Int ) дважды f = f . жplusThree :: Int -> Int plusThree = ( + 3 )main :: IO () main = print ( g 7 ) - 13, где g = дважды плюсThree
J
Явно,
дважды =. наречие : uu y плюстри =. глагол : 'y + 3' г =. плюстри дважды г 7 13
или молчаливо,
дважды =. ^: 2 плюстри =. + & 3 г =. плюстри дважды г 7 13
Java (1.8+)
Используя только функциональные интерфейсы:
import java.util.function. * ;class Main { public static void main ( String [] args ) { Функция < IntUnaryOperator , IntUnaryOperator > дважды = f -> f . andThen ( f ); IntUnaryOperator plusThree = i -> i + 3 ; var g = дважды . применить ( plusThree ); Система . из . Println ( г . applyAsInt ( 7 )); // 13 } }
Или, что то же самое, со статическими методами:
import java.util.function. * ;class Main { частный статический IntUnaryOperator дважды ( IntUnaryOperator f ) { return f . andThen ( f ); } частный статический int plusThree ( int i ) { return i + 3 ; } общественных статический недействительный основной ( Строка [] арг ) { вар г = дважды ( Главная :: plusThree ); Система . из . Println ( г . applyAsInt ( 7 )); // 13 } }
JavaScript
"использовать строго" ;const дважды = f => x => f ( f ( x ));const plusThree = я => я + 3 ;const g = дважды ( plusThree );консоль . журнал ( г ( 7 )); // 13
Юлия
julia> function two ( f ) function result ( x ) return f ( f ( x )) end return result end two (универсальная функция с 1 методом)julia> plusthree ( i ) = i + 3 plusthree (общая функция с 1 методом)джулия> г = дважды ( plusthree ) (:: переменная "# результат # 3" {TypeOf (plusthree)}) (общая функция с 1 методом)Юлия> г ( 7 ) 13
Котлин
весело дважды ( f : ( Int ) -> Int ): ( Int ) -> Int { return { f ( f ( it )) } }веселье plusThree ( i : Int ) = i + 3весело основной () { Вэл г = дважды ( :: plusThree ) println ( g ( 7 )) // 13 }
Lua
локальная функция дважды ( f ) return function ( x ) return f ( f ( x )) end endлокальная функция plusThree ( i ) return i + 3 endместный g = дважды ( plusThree )печать ( г ( 7 )) - 13
MATLAB
функция результат = дважды ( е ) результат = @ внутренний функция val = inner ( x ) val = f ( f ( x )); конецконецplusthree = @ ( i ) i + 3 ; г = дважды ( плюс три ) Дисп ( г ( 7 )); % 13
OCaml
пусть дважды f x = f ( f x )пусть plus_three = (+) 3let () = let g = дважды плюс_три в print_int ( g 7 ); (* 13 *) print_newline ()
PHP
phpобъявить ( strict_types = 1 );функция дважды ( вызываемая $ f ) : Closure { return function ( int $ x ) use ( $ f ) : int { return $ f ( $ f ( $ x )); }; }функция plusThree ( int $ i ) : int { return $ i + 3 ; }$ g = дважды ( 'plusThree' );echo $ g ( 7 ), " \ n " ; // 13
или со всеми функциями в переменных:
phpобъявить ( strict_types = 1 );$ дважды = fn ( вызываемый $ f ) : Closure => fn ( int $ x ) : int => $ f ( $ f ( $ x ));$ plusThree = fn ( int $ i ) : int => $ i + 3 ;$ g = $ дважды ( $ plusThree );echo $ g ( 7 ), " \ n " ; // 13
Обратите внимание, что стрелочные функции неявно захватывают любые переменные, которые поступают из родительской области [1], тогда как анонимные функции требуют, чтобы use
ключевое слово делало то же самое.
Паскаль
{$ mode objfpc}тип fun = function ( x : Integer ) : Integer ;функция дважды ( f : веселье ; x : целое число ) : целое число ;начинать результат : = f ( f ( x )) ;конец ;функция plusThree ( i : Integer ) : Integer ;начинать результат : = i + 3 ;конец ;начинать Writeln ( дважды ( @ plusThree , 7 )) ; {13}конец .
Perl
используйте строгий ; использовать предупреждения ;sub дважды { my ( $ f ) = @_ ; sub { $ f -> ( $ f -> ( @_ )); }; }sub plusThree { мой ( $ i ) = @_ ; $ i + 3 ; }мой $ g = дважды ( \ & plusThree );напечатать $ g -> ( 7 ), "\ n" ; # 13
или со всеми функциями в переменных:
используйте строгий ; использовать предупреждения ;мой $ дважды = sub { мой ( $ f ) = @_ ; sub { $ f -> ( $ f -> ( @_ )); }; };мой $ plusThree = sub { мой ( $ x ) = @_ ; $ x + 3 ; };мой $ g = $ дважды -> ( $ plusThree );напечатать $ g -> ( 7 ), "\ n" ; # 13
Python
>>> def дважды ( f ): ... def result ( x ): ... return f ( f ( x )) ... вернуть результат>>> plusthree = лямбда i : i + 3>>> g = дважды ( плюс три ) >>> g ( 7 ) 13
Синтаксис декоратора Python часто используется для замены функции результатом передачи этой функции через функцию более высокого порядка. Например, функцию g
можно было бы реализовать эквивалентным образом:
>>> @twice ... def g ( i ): ... return i + 3>>> г ( 7 ) 13
р
дважды <- функция ( f ) { return ( function ( x ) { f ( f ( x )) }) }plusThree <- function ( i ) { return ( i + 3 ) }g <- дважды ( plusThree )> print ( g ( 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 также поддерживает синтаксис «остроконечного блока» для лямбда-выражений, которые можно назначать переменной или вызывать анонимно.
Рубин
def дважды ( е ) -> ( х ) { е . позвоните f . call ( x ) } конецplus_three = -> ( я ) { я + 3 }г = дважды ( плюс_три )ставит g . звоните ( 7 ) # 13
Ржавчина
fn дважды ( f : impl Fn ( i32 ) -> i32 ) -> impl Fn ( i32 ) -> i32 { двигаться | х | f ( f ( x )) }fn plus_three ( i : i32 ) -> i32 { я + 3 }fn main () { пусть g = дважды ( plus_three ); println! ( "{}" , g ( 7 )) // 13 }
Scala
объект Main { def дважды ( f : Int => Int ) : Int => Int = f составить f def plusThree ( i : Int ) : Int = i + 3 Защиту основные ( арг : Массив [ Строка ]) : Единица = { Val г = дважды ( plusThree ) print ( g ( 7 )) // 13 } }
Схема
( define ( добавить x y ) ( + x y )) ( define ( f x ) ( lambda ( y ) ( + x y ))) ( display (( f 3 ) 7 )) ( display ( add 3 7 ))
В этом примере схемы функция высшего порядка (f x)
используется для реализации каррирования . Он принимает единственный аргумент и возвращает функцию. Оценка выражения ((f 3) 7)
сначала возвращает функцию после оценки (f 3)
. Возвращенная функция (lambda (y) (+ 3 y))
. Затем он оценивает возвращенную функцию с 7 в качестве аргумента, возвращая 10. Это эквивалентно выражению (add 3 7)
, поскольку (f x)
эквивалентно каррированной форме (add x y)
.
Быстрый
func дважды ( _ f : @ экранирование ( Int ) -> Int ) -> ( Int ) -> Int { return { f ( f ( $ 0 )) } }пусть plusThree = { $ 0 + 3 }пусть g = дважды ( plusThree )print ( g ( 7 )) // 13
Tcl
установить дважды {{ f x } {применить $ f [применить $ f $ x ]}} установить plusThree {{ i } {return [expr $ i + 3 ]}}# результат: 13 пут [применить $ дважды $ плюсТри 7 ]
Tcl использует команду apply для применения анонимной функции (начиная с 8.6).
XACML
Стандарт XACML определяет функции высшего порядка в стандарте для применения функции к нескольким значениям пакетов атрибутов.
rule allowEntry { условие разрешения anyOfAny (функция [ stringEqual ], гражданство , allowedCitizenships ) }
Список функций высшего порядка в XACML можно найти здесь .
XQuery
объявить функцию локальной: дважды ( $ f , $ x ) { $ f ( $ f ( $ x )) };объявить функцию local: plusthree ( $ i ) { $ i + 3 };местный: дважды ( местный: плюстри # 1 , 7 ) (: 13 :)
Альтернативы
Указатели на функции
Указатели функций в таких языках, как C и C ++, позволяют программистам передавать ссылки на функции. Следующий код C вычисляет приближение интеграла произвольной функции:
#include двойной квадрат ( двойной х ) { вернуть х * х ; }двойной куб ( двойной х ) { вернуть х * х * х ; }/ * Вычислить интеграл от f () в интервале [a, b] * / двойной интеграл ( double f ( double x ), double a , double b , int n ) { int i ; двойная сумма = 0 ; двойной dt = ( b - a ) / n ; для ( i = 0 ; i < n ; ++ i ) { сумма + = f ( a + ( i + 0,5 ) * dt ); } return sum * dt ; }int main () { printf ( "% g \ n " , интеграл ( квадрат , 0 , 1 , 100 )); printf ( "% g \ n " , интеграл ( куб , 0 , 1 , 100 )); возврат 0 ; }
Функция qsort из стандартной библиотеки C использует указатель на функцию для имитации поведения функции высшего порядка.
Макросы
Макросы также можно использовать для достижения некоторых эффектов функций высшего порядка. Однако с помощью макросов нелегко избежать проблемы захвата переменных; они также могут привести к большому количеству дублированного кода, что может быть труднее оптимизировать компилятору. Макросы обычно не являются строго типизированными, хотя они могут создавать строго типизированный код.
Оценка динамического кода
В других императивных языках программирования можно достичь некоторых из тех же алгоритмических результатов, которые получаются с помощью функций более высокого порядка путем динамического выполнения кода (иногда называемого операциями Eval или Execute ) в рамках оценки. У такого подхода могут быть существенные недостатки:
- Код аргумента, который должен быть выполнен, обычно не набирается статически ; эти языки обычно полагаются на динамическую типизацию для определения правильности и безопасности кода, который будет выполняться.
- Аргумент обычно предоставляется в виде строки, значение которой может быть неизвестно до времени выполнения. Эта строка должна либо компилироваться во время выполнения программы (с использованием своевременной компиляции ), либо оцениваться путем интерпретации , вызывая некоторые дополнительные накладные расходы во время выполнения и обычно генерируя менее эффективный код.
Объекты
В объектно-ориентированных языках программирования, которые не поддерживают функции высшего порядка, объекты могут быть эффективной заменой. Методы объекта действуют, по сути, как функции, и метод может принимать объекты в качестве параметров и создавать объекты в качестве возвращаемых значений. Однако объекты часто несут дополнительные накладные расходы времени выполнения по сравнению с чистыми функциями и добавляют шаблонный код для определения и создания экземпляра объекта и его метода (ов). Языки, которые разрешают объекты или структуры на основе стека (а не на основе кучи ), могут обеспечить большую гибкость с помощью этого метода.
Пример использования простой записи на основе стека в Free Pascal с функцией, которая возвращает функцию:
пример программы ;тип int = integer ; Txy = запись x , y : int ; конец ; Tf = функция ( xy : Txy ) : int ; функция f ( xy : Txy ) : int ; begin Результат : = xy . у + ху . х ; конец ;функция g ( func : Tf ) : Tf ; начальный результат : = func ; конец ;var a : Tf ; xy : Txy = ( x : 3 ; y : 7 ) ;begin a : = g ( @ f ) ; // возвращаем функцию в "a" writereln ( 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 г ; };// Дефункционализированные реализации приложения функции template < typename F , typename G , typename X > auto apply ( Composition < F , G > f , X arg ) { return apply ( f . F , apply ( f . G , arg )); }template < typename T , typename X > автоматически применяется ( Add < T > f , X arg ) { return arg + f . значение ; }template < typename T , typename X > автоматически применяется ( DivBy < T > f , X arg ) { return arg / f . значение ; }// Шаблон функции компоновки высшего порядка < 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 }, добавить < int > { 5 }); применить ( f , 3 ); // 4.0f apply ( f , 9 ); // 7.0f return 0 ; }
В этом случае используются разные типы для запуска разных функций посредством перегрузки функций . Перегруженная функция в этом примере имеет подпись auto apply
.
Смотрите также
- Первоклассная функция
- Комбинаторная логика
- Программирование на функциональном уровне
- Функциональное программирование
- Исчисление Каппа - формализм для функций, исключающий функции высшего порядка
- Шаблон стратегии
- Сообщения высшего порядка
Рекомендации
- ^ «PHP: функции стрелок - Руководство» . www.php.net . Проверено 1 марта 2021 .