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:
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 .
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.qsortLos 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 aplica la función 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 ( Fs , X , falso ) -> o_en_caso ( Fs , X ); o_en_caso ( Fs , _, { falso , Y } ) -> o_en_caso ( Fs , Y ); o_en_caso (_, _, 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).
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 )) -- 13funció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 " ; // 13o 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 " ; // 13Tenga 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 ) 13dos 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 ); # 13En 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 )) // 13establecer 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:
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.