Función de orden superior

Este artículo incluye una lista de referencias generales , pero carece de suficientes citas en línea correspondientes . Por favor, ayude a mejorar este artículo introduciendo citas más precisas. ( Septiembre de 2013 ) ( Aprenda cómo y cuándo eliminar este mensaje )

En matemáticas y ciencias de la computación , una función de orden superior ( HOF ) es una función que realiza al menos una de las siguientes acciones:

• toma una o más funciones como argumentos (es decir, un parámetro de procedimiento , que es un parámetro de un procedimiento que es en sí mismo un procedimiento),
• devuelve una función o valor como su resultado.

Todas las demás funciones son funciones de primer orden . En matemáticas, las funciones de orden superior también se denominan operadores o funcionales . El operador diferencial en cálculo es un ejemplo común, ya que asigna una función a su derivada , que también es una función. Las funciones de orden superior no deben confundirse con otros usos de la palabra "functor" en las matemáticas, véase Functor (desambiguación) .

En el cálculo lambda no tipado , todas las funciones son de orden superior; en un cálculo lambda tipado , del cual se derivan la mayoría de los lenguajes de programación funcional , las funciones de orden superior que toman una función como argumento son valores con tipos de la forma .${\displaystyle (\tau _{1}\to \tau _{2})\to \tau _{3}}$

• mapLa función, presente en muchos lenguajes de programación funcional, es un ejemplo de una función de orden superior. Toma como argumentos una función f y una colección de elementos y, como resultado, devuelve una nueva colección con f aplicada a cada elemento de la colección.
• Funciones de ordenación, que toman una función de comparación como parámetro, lo que permite al programador separar el algoritmo de ordenación de las comparaciones de los elementos que se ordenan. La función estándar de C es un ejemplo de esto. qsort
• filtrar
• doblar
• aplicar
• Composición de funciones
• Integración
• Llamar de vuelta
• Travesía de árboles
• La gramática de Montague , una teoría semántica del lenguaje natural, utiliza funciones de orden superior.

Los ejemplos no pretenden comparar y contrastar lenguajes de programación, sino servir como ejemplos de sintaxis de funciones de orden superior.

En los siguientes ejemplos, la función de orden superior twicetoma una función y la aplica a un valor dos veces. Si twicese debe aplicar varias veces para lo mismo, fes preferible que devuelva una función en lugar de un valor. Esto está en línea con el principio de " no repetirse ".

 dos veces ← { ⍺⍺ ⍺⍺ ⍵ }   más tres ← { ⍵ + 3 } g ← { más tres dos veces ⍵ } g 7 13     

O de manera tácita:

 dos veces ← ⍣ 2 mástres ← + ∘ 3 g ← más tres dos veces g 7 13    

Usando std::functionen C++11 :

#include <iostream> #include <funcional>  auto dos veces = []( const std :: función < int ( int ) >& f ) { return [ f ]( int x ) { return f ( f ( x )); }; };            auto más_tres = []( int i ) { return i + 3 ; };        int main () { auto g = dos veces ( más_tres );      estándar :: cout << g ( 7 ) << '\n' ; // 13 }     

O bien, con lambdas genéricas proporcionadas por C++14:

#include <flujo de datos> auto dos veces = []( const auto & f ) { return [ f ]( int x ) { return f ( f ( x )); }; };            auto más_tres = []( int i ) { return i + 3 ; };        int main () { auto g = dos veces ( más_tres );      estándar :: cout << g ( 7 ) << '\n' ; // 13 }     

Usando sólo delegados:

usando Sistema ; clase pública Programa { public static void Main ( string [] args ) { Func < Func < int , int > , Func < int , int >> dos veces = f => x => f ( f ( x ));                    Func < int , int > másTres = i => i + 3 ;         var g = dos veces ( másTres );    Consola .WriteLine ( g ( 7 )); // 13 } }  

O equivalentemente, con métodos estáticos:

usando Sistema ; clase pública Programa { privada estática Func < int , int > Twice ( Func < int , int > f ) { return x => f ( f ( x )); }                privado estático int PlusThree ( int i ) => i + 3 ;         public static void Main ( string [] args ) { var g = Twice ( PlusThree );          Consola .WriteLine ( g ( 7 )); // 13 } }  

( defn dos veces [ f ] ( fn [ x ] ( f ( f x ))))     ( defn más tres [ i ] ( + i 3 ))   ( def g ( dos veces más tres ))  ( println ( g 7 )) ; 13  

dos veces  =  función ( f )  {  devolver  función ( x )  {  devolver  f ( f ( x ));  }; };plusThree  =  función ( i )  {  devolver  i  +  3 ; };g  =  dos veces ( más tres );escribirSalida ( g ( 7 ));  // 13

( defun dos veces ( f ) ( lambda ( x ) ( funcall f ( funcall f x )))) ( defun más tres ( i ) ( + i 3 )) ( defvar g ( dos veces #' más tres )) ( print ( funcall g 7 ))                            

importar std . stdio : writeln ;   alias dos veces = ( f ) => ( int x ) => f ( f ( x ));        alias másTres = ( int i ) => i + 3 ;        void main () { auto g = dos veces ( másTres );      escrituraln ( g ( 7 )); // 13 } 

int Función ( int ) dos veces ( int Función ( int ) f ) { return ( x ) { return f ( f ( x )); }; }           int másTres ( int i ) { return i + 3 ; }       void main () { final g = dos veces ( másTres ); print ( g ( 7 )); // 13 }         

En Elixir, puedes mezclar definiciones de módulos y funciones anónimas

defmodule Hof hacer def dos veces ( f ) hacer fn ( x ) -> f . ( f . ( x )) fin fin fin          más_tres = fn ( i ) -> i + 3 fin       g = Hof . dos veces ( más tres )  IO . pone g . ( 7 ) #13  

Alternativamente, también podemos componer utilizando funciones anónimas puras.

dos veces = fn ( f ) -> fn ( x ) -> f . ( f . ( x )) fin fin       más_tres = fn ( i ) -> i + 3 fin       g = dos veces . ( más tres )  IO . pone g . ( 7 ) #13  

o_en caso contrario ([], _) -> falso ; o_en caso contrario ([ F | Fs ], X ) -> o_en caso contrario ( Fs , X , F ( X )).          o_en caso contrario ( Fs , X , falso ) -> o_en caso contrario ( Fs , X ); o_en caso contrario ( Fs , _, { falso , Y }) -> o_en caso contrario ( Fs , Y ); o_en caso contrario (_, _, R ) -> R .               o_sino ([ fun erlang : es_entero / 1 , fun erlang : es_átomo / 1 , fun erlang : es_lista / 1 ], 3 . 23 ).      

En este ejemplo de Erlang, la función de orden superior or_else/2toma una lista de funciones ( Fs) y argumento ( X). Evalúa la función Fcon el argumento Xcomo argumento. Si la función devuelve falso, se evaluará Fla siguiente función en . Si la función devuelve , se evaluará la siguiente función en con argumento . Si la función devuelve , la función de orden superior devolverá . Tenga en cuenta que , , y pueden ser funciones. El ejemplo devuelve .FsF{false, Y}FsYFRor_else/2RXYRfalse

sea ​​dos veces f = f >> f      sea ​​más_tres = (+) 3    sea ​​g = dos veces más tres    g 7 |> printf "%A" // 13     

paquete principal importar "fmt" func dos veces ( 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 := dos veces ( más tres )  fmt . Imprimir ( g ( 7 )) // 13 } 

Tenga en cuenta que una función literal se puede definir con un identificador ( twice) o de forma anónima (asignado a la variable plusThree).

def dos veces = { f , x -> f ( f ( x )) } def másTres = { it + 3 } def g = dos veces . curry ( másTres ) println g ( 7 ) // 13                     

dos veces : :( Int -> Int ) -> ( Int -> Int ) dos veces f = f . f             masTres :: Int -> Int masTres = ( + 3 )      main :: IO () main = print ( g 7 ) --13 donde g = dos veces más tres             

Explícitamente,

 dos veces = adverbio : 'uu y'    mástres =. verbo : 'y + 3' g =. mástres dos veces g 7 13          

o tácitamente,

 dos veces =. ^: 2  más tres =. +& 3 g =. más tres dos veces g 7 13        

Usando solo interfaces funcionales:

importar java.util.function.* ; clase  Main { public static void main ( String [] args ) { Función < IntUnaryOperator , IntUnaryOperator > dos veces = f -> f . andThen ( f );               OperadorIntUnariomásTres = i - > i + 3 ;        var g = twice.apply ( plusThree ) ;​    Sistema . out . println ( g . applyAsInt ( 7 )); // 13 } }  

O equivalentemente, con métodos estáticos:

importar java.util.function.* ; clase  Main { privada estática IntUnaryOperator twice ( IntUnaryOperator f ) { return f . andThen ( f ); }           privado estático int plusThree ( int i ) { return i + 3 ; }           public static void main ( String [] args ) { var g = twice ( Main :: plusThree );          Sistema . out . println ( g . applyAsInt ( 7 )); // 13 } }  

Con funciones de flecha:

"utilizar estricto" ;const dos veces = f => x => f ( f ( x ));       const másTres = i => i + 3 ;       const g = dos veces ( másTres );   consola .log ( g ( 7 )); // 13 

O con sintaxis clásica:

"utilizar estricto" ;función dos veces ( f ) { devolver función ( x ) { devolver f ( f ( x )); }; }         función plusThree ( i ) { return i + 3 ; }      const g = dos veces ( másTres );   consola .log ( g ( 7 )); // 13 

julia> función dos veces ( f ) función resultado ( x ) devolver f ( f ( x )) fin devolver resultado fin dos veces (función genérica con 1 método)          julia> plusthree ( i ) = i + 3 plusthree (función genérica con 1 método)     julia> g = dos veces ( más tres ) (::var"#result#3"{typeof(más tres)}) (función genérica con 1 método)   Julia> g ( 7 ) 13 

diversión dos veces ( f : ( Int ) -> Int ): ( Int ) -> Int { return { f ( f ( it )) } }            diversión másTres ( i : Int ) = i + 3      diversión principal () { val g = dos veces ( :: másTres )       println ( g ( 7 )) // 13 } 

función  dos veces ( f )  devolver  función  ( x )  devolver  f ( f ( x ))  fin finfunción  plusThree ( i )  devuelve  i  +  3 fin g  local =  dos veces ( más tres )imprimir ( g ( 7 ))  -- 13

función  resultado = dos veces ( f ) resultado = @( x ) f ( f ( x )); fin     mástres = @( i ) i + 3 ;     g = dos veces ( más tres )  disp ( g ( 7 )); % 13 

sea  ​​dos veces  f  x  =  f  ( f  x )sea  ​​más_tres  =  (+)  3sea  ​​()  =  sea  g  =  dos veces  más tres  en print_int  ( g  7 );  (* 13 *)  print_newline  ()

<?phpdeclarar ( tipos_estrictos = 1 );función  dos veces ( invocable  $f ) :  Cierre  {  return  function  ( int  $x )  use  ( $f ) :  int  {  return  $f ( $f ( $x ));  }; }función  másTres ( int  $i ) :  int  {  return  $i  +  3 ; }$g  =  dos veces ( 'másTres' );echo  $g ( 7 ),  " \n " ;  // 13

o con todas las funciones en variables:

<?phpdeclarar ( tipos_estrictos = 1 );$twice  =  fn ( invocable  $f ) :  Cierre  =>  fn ( int  $x ) :  int  =>  $f ( $f ( $x ));$másTres  =  fn ( int  $i ) :  int  =>  $i  +  3 ;$g  =  $dos veces ( $másTres );echo  $g ( 7 ),  " \n " ;  // 13

Tenga en cuenta que las funciones de flecha capturan implícitamente cualquier variable que provenga del ámbito principal, ^[1] mientras que las funciones anónimas requieren la usepalabra clave para hacer lo mismo.

utilizar estricto ; utilizar advertencias ;  sub dos veces { mi ( $f ) = @_ ; sub { $f -> ( $f -> ( @_ )); }; }          sub másTres { mi ( $i ) = @_ ; $i + 3 ; }         mi $g = dos veces ( \& másTres );   imprimir $g -> ( 7 ), "\n" ; # 13   

o con todas las funciones en variables:

utilizar estricto ; utilizar advertencias ;  mi $dos veces = sub { mi ( $f ) = @_ ; sub { $f -> ( $f -> ( @_ )); }; };            mi $másTres = sub { mi ( $i ) = @_ ; $i + 3 ; };           mi $g = $twice -> ( $plusThree );   imprimir $g -> ( 7 ), "\n" ; # 13   

>>> def  dos veces ( f ): ...  def  resultado ( x ): ...  return  f ( f ( x )) ...  return  resultado>>> más_tres  =  lambda  i :  i  +  3>>> g  =  dos veces ( más tres ) >>> g ( 7 ) 13 

La sintaxis del decorador de Python se utiliza a menudo para reemplazar una función con el resultado de pasar esa función a través de una función de orden superior. Por ejemplo, la función gpodría implementarse de forma equivalente:

>>> @twice ... def  g ( i ): ...  devuelve  i  +  3>>> g ( 7 ) 13

dos veces <- \ ( f ) \ ( x ) f ( f ( x ))    plusThree <- función ( i ) i + 3     g <- dos veces ( más tres )  > g ( 7 ) [ 1 ] 13  

sub  dos veces ( Callable:D  $f ) { return  sub { $f ( $f ( $^x )) };}sub  másTres ( Int:D  $i ) { return  $i + 3 ;}mi  $g = dos veces ( &plusTres );diga  $g ( 7 ); # 13

En Raku, todos los objetos de código son cierres y, por lo tanto, pueden hacer referencia a variables "léxicas" internas desde un ámbito externo porque la variable léxica está "cerrada" dentro de la función. Raku también admite la sintaxis de "bloque puntiagudo" para expresiones lambda que se pueden asignar a una variable o invocar de forma anónima.

def dos veces ( f ) -> ( x ) { f . call ( f . call ( x )) } fin     más_tres = -> ( i ) { i + 3 }       g = dos veces ( más tres )  pone g.llamada ( 7 ) # 13​  

fn  dos veces ( f : impl Fn ( i32 ) -> i32 ) -> impl Fn ( i32 ) -> i32 { mover | x | f ( f ( x )) }         fn  plus_three ( i : i32 )  -> i32  { i + 3 }   fn  main () { sea g = dos veces ( más_tres );      imprimir! ( "{}" , g ( 7 )) // 13 }  

objeto Principal { def dos veces ( f : Int => Int ): Int => Int = f componer f               def másTres ( i : Int ): Int = i + 3        def main ( args : Matriz [ Cadena ]): Unidad = { val g = dos veces ( másTres )          imprimir ( g ( 7 )) // 13 } }  

( definir ( componer f g ) ( lambda ( x ) ( f ( g x ))))         ( definir ( dos veces f ) ( componer f f ))      ( definir ( más tres i ) ( + i 3 ))     ( define g ( dos veces más tres ))   ( mostrar ( g 7 )) ; 13 ( mostrar " \n " )    

func  dos veces ( _  f :  @ escapando  ( Int )  ->  Int )  ->  ( Int )  ->  Int  {  return  {  f ( f ( $0 ))  } }sea  ​​másTres  =  {  $0  +  3  }sea  ​​g  =  dos veces ( más tres )imprimir ( g ( 7 ))  // 13

establecer  dos veces {{ f x } {aplicar $f [aplicar $f $x ]}} establecer másTres {{ i } {devolver [expr $i + 3 ]}}              # resultado: 13 puts [aplicar $dos veces $másTres 7 ]    

Tcl usa el comando apply para aplicar una función anónima (desde 8.6).

El estándar XACML define funciones de orden superior en el estándar para aplicar una función a múltiples valores de bolsas de atributos.

regla allowEntry { permitir condición anyOfAny(función [ stringEqual ], ciudadanías , allowedCitizenships ) }      

La lista de funciones de orden superior en XACML se puede encontrar aquí .

declarar función local:twice ( $ f , $ x ) { $ f ( $ f ( $ x )) };     declarar función local:plusthree ( $ i ) { $ i + 3 };      local:dos veces ( local:mástres # 1 , 7 ) (:13 :)  

Los punteros de función en lenguajes como C , C++ , Fortran y Pascal permiten a los programadores pasar referencias a funciones. El siguiente código C calcula una aproximación de la integral de una función arbitraria:

#incluir <stdio.h> doble cuadrado ( doble x ) { devolver x * x ; }      doble cubo ( doble x ) { devolver x * x * x ; }        /* Calcular la integral de f() dentro del intervalo [a,b] */ double integral ( double f ( double x ), double a , double b , int n ) { int i ; double suma = 0 ; double dt = ( b - a ) / n ; for ( i = 0 ; i < n ; ++ i ) { suma += f ( a + ( i + 0.5 ) * dt ); } return suma * dt ; }                                              int main () { printf ( "%g \n " , integral ( cuadrado , 0 , 1 , 100 )); printf ( "%g \n " , integral ( cubo , 0 , 1 , 100 )); return 0 ; }             

La función qsort de la biblioteca estándar C utiliza un puntero de función para emular el comportamiento de una función de orden superior.

Las macros también se pueden utilizar para lograr algunos de los efectos de las funciones de orden superior. Sin embargo, las macros no pueden evitar fácilmente el problema de la captura de variables; también pueden generar grandes cantidades de código duplicado, lo que puede resultar más difícil de optimizar para un compilador. Las macros generalmente no están fuertemente tipadas, aunque pueden producir código fuertemente tipado.

En otros lenguajes de programación imperativa , es posible lograr algunos de los mismos resultados algorítmicos que se obtienen a través de funciones de orden superior mediante la ejecución dinámica de código (a veces llamadas operaciones Eval o Execute ) en el ámbito de la evaluación. Este enfoque puede tener importantes desventajas:

• El código de argumento a ejecutar normalmente no está tipado estáticamente ; estos lenguajes generalmente se basan en la tipificación dinámica para determinar la correcta formación y la seguridad del código a ejecutar.
• El argumento se proporciona generalmente como una cadena, cuyo valor puede no conocerse hasta el momento de la ejecución. Esta cadena debe compilarse durante la ejecución del programa (mediante la compilación en tiempo real ) o evaluarse mediante interpretación , lo que genera una sobrecarga adicional en el momento de la ejecución y, por lo general, genera un código menos eficiente.

En los lenguajes de programación orientados a objetos que no admiten funciones de orden superior, los objetos pueden ser un sustituto eficaz. Los métodos de un objeto actúan en esencia como funciones, y un método puede aceptar objetos como parámetros y producir objetos como valores de retorno. Sin embargo, los objetos suelen conllevar una sobrecarga de tiempo de ejecución adicional en comparación con las funciones puras, y un código repetitivo adicional para definir e instanciar un objeto y su(s) método(s). Los lenguajes que permiten objetos o estructuras basados ​​en pila (en lugar de basados ​​en montón ) pueden proporcionar más flexibilidad con este método.

Un ejemplo de uso de un registro simple basado en pila en Free Pascal con una función que devuelve una función:

ejemplo de programa ; tipo int = entero ; Txy = registro x , y : int ; fin ; Tf = función ( xy : Txy ) : int ; función f ( xy : Txy ) : int ; comienzo Resultado := xy . y + xy . x ; fin ;                             función g ( func : Tf ) : Tf ; inicio resultado := func ; fin ;         var a : Tf ; xy : Txy = ( x : 3 ; y : 7 ) ;          begin a := g ( @ f ) ; // devuelve una función a "a" writeln ( a ( xy )) ; // imprime 10 end .       

La función a()toma un Txyregistro como entrada y devuelve el valor entero de la suma de los registros xy ylos campos (3 + 7).

La desfuncionalización se puede utilizar para implementar funciones de orden superior en lenguajes que carecen de funciones de primera clase :

// Estructuras de datos de funciones desfuncionalizadas plantilla < typename T > struct Add { T value ; }; plantilla < typename T > struct DivBy { T value ; }; plantilla < typename F , typename G > struct Composition { F f ; G g ; };                         // Plantilla de implementación de aplicaciones de funciones desfuncionalizadas < typename F , typename G , typename X > auto apply ( Composition < F , G > f , X arg ) { return apply ( f . f , apply ( f . g , arg )); }               plantilla < typename T , typename X > aplicar automáticamente ( Agregar < T > f , X arg ) { devolver arg + f . valor ; }            plantilla < typename T , typename X > aplicar automáticamente ( DivBy < T > f , X arg ) { devolver arg / f . valor ; }            // Plantilla de función de composición de orden superior < typename F , typename G > Composición < F , G > compose ( F f , G g ) { return Composición < F , G > { f , g }; }              int main ( int argc , const char * argv []) { auto f = componer ( DivBy < float > { 2.0f }, Add < int > { 5 }); aplicar ( f , 3 ); // 4.0f aplicar ( f , 9 ); // 7.0f devolver 0 ; }                       

En este caso, se utilizan distintos tipos para activar distintas funciones mediante la sobrecarga de funciones . La función sobrecargada en este ejemplo tiene la firma auto apply.

• Función de primera clase
• Lógica combinatoria
• Programación a nivel de función
• Programación funcional
• Cálculo kappa : un formalismo para funciones que excluye funciones de orden superior
• Patrón de estrategia
• Mensajes de orden superior