Функция высшего порядка

Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Сентябрь 2013 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

В математике и информатике , функция высшего порядка является функцией , которая делает по крайней мере , одно из следующих действий :

• принимает одну или несколько функций в качестве аргументов (то есть процедурных параметров ),
• возвращает функцию в качестве своего результата.

Все остальные функции являются функциями первого порядка . В математике функции высшего порядка также называют операторами или функционалами . Дифференциальный оператор в исчислении является типичным примером, так как он отображает функцию его производную , также функция. Функции высшего порядка не следует путать с другим использованием слова «функтор» в математике, см. Функтор (значения) .

В нетипизированном лямбда-исчислении все функции имеют высший порядок; в типизированном лямбда-исчислении , от которого происходит большинство функциональных языков программирования, функции высшего порядка, которые принимают одну функцию в качестве аргумента, являются значениями с типами формы .${\ Displaystyle (\ тау _ {1} \ к \ тау _ {2}) \ к \ тау _ {3}}$

Общие примеры [ править ]

• mapФункция, встречающаяся во многих языках функционального программирования, является одним из примеров функции высшего порядка. Он принимает в качестве аргументов функцию f и набор элементов, и в результате возвращает новую коллекцию с f, примененным к каждому элементу из коллекции.
• Функции сортировки, которые принимают функцию сравнения в качестве параметра, позволяя программисту отделить алгоритм сортировки от сравнений сортируемых элементов. C стандартная функция qsort является примером этого.
• фильтр
• складывать
• подать заявление
• Состав функций
• Интеграция
• Перезвоните
• Обход дерева
• Грамматика Монтегю , семантическая теория естественного языка, использует функции высшего порядка

Поддержка языков программирования [ править ]

Было предложено разделить эту статью на новую статью под названием « Сравнение языков программирования (функции высшего порядка)» . ( Обсудить ) ( май 2016 )

Прямая поддержка [ править ]

Примеры не предназначены для сравнения и противопоставления языков программирования, а служат в качестве примеров синтаксиса функций высшего порядка.

В следующих примерах функция высшего порядка twiceпринимает функцию и дважды применяет ее к некоторому значению. Если twiceдля одного и того же необходимо применить несколько раз, fон предпочтительно должен возвращать функцию, а не значение. Это соответствует принципу « не повторяйся ».

APL [ править ]

 plusthree ← { ⍵ + 3 } дважды ← { ⍺⍺  ⍺⍺  ⍵ } g ← { плюстри  дважды  ⍵ }  г  7 13

Или молчаливо:

 плюстри ← + ∘ 3 дважды ← ⍣ 2 g ← плюстри  дважды  г  7 13

C [ править ]

С указателями функций в C:

#include  <stdio.h>ЬурейеЕ  междунар  ( * int_func_int )  ( INT );int  дважды ( int_func_int  f ,  int  x )  { return  f ( f ( x )); }int  plusthree ( int  я )  { вернуть  я  +  3 ; }int  main ( void )  { printf ( "% d \ n " ,  дважды ( plusthree ,  7 ));  // 13 }

C ++ [ править ]

Использование std::functionв C ++ 11:

#include  <iostream>#include  <функциональный>авто  дважды  =  [] ( const  std :: function < int ( int ) > &  f ,  int  x ) {  return  f ( f ( x )); }; auto  plus_three  =  [] ( int  я ) {  вернуть  я  +  3 ; }; int  main () {  std :: cout  <<  дважды ( plus_three ,  7 )  <<  '\ n' ;  // 13 }

Или с общими лямбдами, предоставляемыми C ++ 14:

#include  <iostream>авто  дважды  =  [] ( авто  f ,  int  x ) {  return  f ( f ( x )); }; auto  plus_three  =  [] ( int  я ) {  вернуть  я  +  3 ; }; int  main () {  std :: cout  <<  дважды ( plus_three ,  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 ; Консоль . WriteLine ( дважды ( plusThree ) ( 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 )  {  Консоль . WriteLine ( Дважды ( ПлюсТри ) ( 7 ));  // 13  } }

Clojure [ править ]

( defn дважды  [ f  x ]  ( f  ( f  x )))( defn plus-three  [ i ]  ( + i  3 ))( println ( дважды  плюс три  7 ))  ; 13

Язык разметки ColdFusion (CFML) [ править ]

дважды  =  функция ( f ,  x )  {  return  f ( f ( x )); };plusThree  =  function ( i )  {  return  i  +  3 ; };writeOutput ( дважды ( plusThree ,  7 ));  // 13

D [ править ]

импорт  std . stdio  :  Writeln ;псевдоним  дважды  =  ( f ,  x )  =>  f ( f ( x )); псевдоним  plusThree  =  ( int  i )  =>  i  +  3 ;void  main () {  Writeln ( дважды ( plusThree ,  7 ));  // 13 }

Эликсир [ править ]

В Elixir вы можете смешивать определения модулей и анонимные функции.

defmodule  Hof  do  def  дважды ( f ,  x )  do  f . ( f . ( x ))  конец конецplus_three  =  fn ( i )  ->  3  +  i  конецIO . ставит  Хоф . дважды ( plus_three ,  7 )  # 13

В качестве альтернативы мы также можем составлять, используя чистые анонимные функции.

дважды  =  fn ( f ,  x )  ->  f . ( f . ( x ))  конец plus_three  =  fn ( i )  ->  3  +  i  конецIO . ставит  дважды . ( плюс_три ,  7 )  # 13

Эрланг [ править ]

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дважды  plus_three  7  |>  printf  "% A"  // 13

Перейти [ править ]

 основной пакетимпорт  "fmt"func  дважды ( f  func ( int )  int ,  x  int )  int  { return  f ( f ( x )) }func  main ()  { plusThree  : =  func ( i  int )  int  { return  i  +  3 }fmt . Println ( дважды ( plusThree ,  7 ))  // 13 }

Обратите внимание, что функциональный литерал может быть определен либо с идентификатором ( twice), либо анонимно (назначен переменной f).

Haskell [ править ]

дважды  ::  ( а  ->  а )  ->  ( а  ->  а ) дважды  f  =  f  .  жplusThree  ::  Num  a  =>  a  ->  a plusThree  i  =  i  +  3main  ::  IO  () main  =  print  ( дважды  плюс три  7 )  - 13

Или более кратко:

дважды  f  =  f  .  е основные  =  напечатать  $ в  два раза  ( + 3 )  7  - 13

J [ править ]

Ясно,

 дважды =.  наречие  :  'uu y'  plusthree =.  глагол  :  'y + 3'  г =.  плюстри  дважды  г  7 13

или молчаливо,

 дважды =.  ^: 2  плюс три =.  + & 3  г =.  плюстри  дважды  г  7 13

или безточечный стиль,

 + & 3 ( ^: 2 )  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 ; Система . из . println ( дважды . применить ( plusThree ). applyAsInt ( 7 ));  // 13  } }

Или, что то же самое, статическими методами:

import  java.util.function. * ;class  Main  {  частный  статический  IntUnaryOperator  дважды ( IntUnaryOperator  f )  {  return  f . andThen ( f );  } частный  статический  int  plusThree ( int  i )  {  return  i  +  3 ;  } public  static  void  main ( String []  args )  {  System . из . println ( дважды ( Main :: plusThree ). applyAsInt ( 7 ));  // 13  } }

JavaScript [ править ]

const  дважды  =  ( f ,  x )  =>  f ( f ( x ));const  plusThree  =  я  =>  я  +  3 ;консоль . журнал ( дважды ( 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

Котлин [ править ]

весело  < T >  дважды ( f :  ( T )  ->  T ):  ( T )  ->  T  {  return  {  f ( f ( it ))  } }удовольствие  f ( я :  Int )  =  я  +  3весело  основной ()  {  Println ( дважды ( :: е ) ( 7 ))  // 13 }

Lua [ править ]

локальная  функция  дважды ( f ,  x )  return  f ( f ( x )) endлокальная  функция  addthree ( i )  return  i  +  3 endprint ( дважды ( addthree ,  7 ))  - 13

MATLAB [ править ]

 результат функции = дважды ( f, x )  результат  =  f ( f ( x )); конецplusthree  =  @ ( i )  i  +  3 ;disp ( дважды ( плюстри ,  7 ));  % 13

OCaml [ править ]

Явно

пусть  дважды  f  x  =  f  ( f  x )пусть  plus_three  i  =  i  +  3let  ()  =  print_int  ( дважды  плюс_три  7 )  (* 13 *)

Одна линия

let  ()  =  print_int  (( удовольствие  f  x  ->  f  ( f  x ))  ((+)  3 )  7 )  (* 13 *)

PHP [ править ]

<? phpобъявить ( strict_types = 1 );функция  дважды ( вызываемая  $ f ,  int  $ x ) :  int  {  return  $ f ( $ f ( $ x )); }функция  addThree ( int  $ i ) :  int  {  return  $ i  +  3 ; }эхо  дважды ( 'addThree' ,  7 ),  " \ n " ;  // 13

или со всеми функциями в переменных:

<? phpобъявить ( strict_types = 1 );$ дважды  =  fn  ( вызываемый  $ f ,  int  $ x ) :  int  =>  $ f ( $ f ( $ x ));$ addThree  =  fn  ( int  $ i ) :  int  =>  $ i  +  3 ;echo  $ дважды ( $ addThree ,  7 ),  " \ n " ;  // 13

Паскаль [ править ]

{$ 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 ; }напечатайте  дважды ( \ & plusThree ) -> ( 7 ),  "\ n" ;  # 13

или со всеми функциями в переменных:

используйте  строгий ; использовать  предупреждения ;мой  $ дважды  =  sub  {  мой  ( $ f )  =  @_ ;  sub  {  $ f -> ( $ f -> ( @_ ));  }; };мой  $ plusThree  =  sub  {  мой  ( $ x )  =  @_ ;  $ x  +  3 ; };напечатайте  $ дважды -> ( $ plusThree ) -> ( 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

R [ править ]

дважды  <-  функция ( 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 ;}скажите  дважды ( & plusThree ) ( 7 ); # 13

В Raku все объекты кода являются замыканиями и, следовательно, могут ссылаться на внутренние «лексические» переменные из внешней области видимости, потому что лексическая переменная «закрыта» внутри функции. Raku также поддерживает синтаксис «остроконечного блока» для лямбда-выражений, которые можно назначать переменной или вызывать анонимно.

Руби [ править ]

def  дважды ( f ,  x )  f . позвоните  f . вызов ( x ) конецplus_three  =  -> ( i )  {  i  +  3  } ставит  дважды ( plus_three ,  7 )  # => 13

Ржавчина [ править ]

fn  дважды < T > ( f : impl Fn ( T ) -> T ) -> impl Fn ( T ) -> T {       двигаться | х | f ( f ( x ))  }fn  plus_three ( i : i32 )  -> i32  { я + 3  }fn  main () {  println ! ( "{}" , дважды ( plus_three ) ( 7 )) // 13 }  

Scala [ править ]

объект  Main  {  def  дважды ( f :  Int  =>  Int ) :  Int  =>  Int  =  f  составить  f def  plusThree ( i :  Int ) :  Int  =  i  +  3 Защиту  основные ( арг :  Массив [ Строка ]) :  Unit  =  печать ( дважды ( plusThree ) ( 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).

Swift [ править ]

// универсальная функция func  дважды < T > ( _  f :  @ escaping  ( T )  ->  T )  ->  ( T )  ->  T  {  return  {  f ( f ( $ 0 ))  } }// предполагаемое закрытие let  plusThree  =  {  $ 0  +  3  }print ( дважды ( plusThree ) ( 7 ))  // 13

Tcl [ править ]

установить дважды {{ f x }  {применить  $ f  [применить  $ f  $ x ]}} установить plusThree {{ i }  {return  [expr  $ i  +  3 ]}}# результат: 13 пут  [применить  $ дважды  $ плюсТри  7 ]

Tcl использует команду apply для применения анонимной функции (начиная с 8.6).

Wolfram Language [ править ]

В [ 1 ] : = Twice = Nest [ # 1 , # 2 , 2 ] & ;     В [ 2 ] : = Дважды [ # + 3 & , 7 ]     Из [ 2 ] = 13 

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  <stdio.h>двойной  квадрат ( двойной  х ) {  вернуть  х  *  х ; }двойной  куб ( двойной  х ) {  вернуть  х  *  х  *  х ; }/ * Вычислить интеграл от f () в интервале [a, b] * / двойной  интеграл ( double  f ( double  x ),  double  a ,  double  b ,  int  n ) {  int  i ;  двойная  сумма  =  0 ;  двойной  dt  =  ( b  -  a )  /  n ;  for  ( 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.

См. Также [ править ]

• Первоклассная функция
• Комбинаторная логика
• Программирование на функциональном уровне
• Функциональное программирование
• Исчисление Каппа - формализм для функций, исключающий функции высшего порядка
• Шаблон стратегии
• Сообщения высшего порядка

Ссылки [ править ]