En matemáticas e informática , 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 , también una función. Las funciones de orden superior no deben confundirse con otros usos de la palabra "functor" en matemáticas, consulte Functor (desambiguación) .
En el cálculo lambda sin tipo , 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 funcionales , las funciones de orden superior que toman una función como argumento son valores con tipos de la forma .
map
La función, que se encuentra en muchos lenguajes de programación funcionales, 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.qsort
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 twice
toma una función y la aplica a algún valor dos veces. Si twice
tiene que aplicarse varias veces para lo mismo, f
preferiblemente debería devolver una función en lugar de un valor. Esto está en consonancia con el principio de " no repetirse ".
dos veces ← { ⍺⍺ ⍺⍺ ⍵ } mástres ← { ⍵ + 3 } g ← { más tres dos veces ⍵ } g 7 13
O de manera tácita:
dos veces ← ⍣ 2 más tres ← + ∘ 3 g ← más tres dos veces g 7 13
Usando std::function
en C++11 :
#incluir <iostream> #incluir <funcional> auto dos veces = []( const std :: function < int ( int ) >& f ) { return [ f ]( int x ) { return f ( f ( x )); }; }; auto plus_tres = []( int i ) { return i + 3 ; }; int main () { auto g = dos veces ( más_tres ); std :: cout << g ( 7 ) << '\n' ; // 13 }
O, con lambdas genéricas proporcionadas por C++14:
#incluir <iostream> auto dos veces = []( const auto & f ) { return [ f ]( int x ) { return f ( f ( x )); }; }; auto plus_tres = []( int i ) { return i + 3 ; }; int main () { auto g = dos veces ( más_tres ); std :: cout << g ( 7 ) << '\n' ; // 13 }
Usando solo delegados:
usando Sistema ; programa de clase pública { 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 de manera equivalente, con métodos estáticos:
usando Sistema ; programa de clase pública { función estática privada < int , int > dos veces ( Func < int , int > f ) { return x => f ( f ( x )); } privado estático int PlusThree ( int i ) => i + 3 ; public static void Principal ( cadena [] args ) { var g = Dos veces ( PlusThree ); Consola . WriteLine ( g ( 7 )); // 13 } }
( definir 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 ) { función de retorno ( x ) { devolución f ( f ( x )); }; }; másTres = función ( i ) { return i + 3 ; };g = dos veces ( másTres );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 estándar . stdio : escrito ; alias dos veces = ( f ) => ( int x ) => f ( f ( x )); alias másTres = ( int i ) => i + 3 ; void main () { auto g = dos veces ( másTres ); escrito ( g ( 7 )); // 13 }
int Función ( int ) dos veces ( int Función ( int ) f ) { retorno ( x ) { retorno f ( f ( x )); }; } int másTres ( int i ) { return i + 3 ; } void main () { final g = dos veces ( másTres ); imprimir ( 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 plus_tres = fn ( i ) -> i + 3 final gramo = Hof . dos veces ( más_tres ) OÍ . 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 plus_tres = fn ( i ) -> i + 3 final g = dos veces . ( más_tres ) OÍ . pone g . ( 7 ) #13
o_else ([], _) -> falso ; o_else ([ F | Fs ], X ) -> o_else ( Fs , X , F ( X )). or_else ( Fs , X , falso ) -> or_else ( Fs , X ); o_else ( Fs , _, { falso , Y }) -> o_else ( Fs , Y ); o_else (_, _, R ) -> R . or_else ([ erlang divertido : is_integer / 1 , erlang divertido : is_atom / 1 , erlang divertido : is_list / 1 ] , 3. 23 ) .
En este ejemplo de Erlang, la función de orden superior or_else/2
toma una lista de funciones ( Fs
) y argumento ( X
). Evalúa la función F
con el argumento X
como argumento. Si la función devuelve falso, se evaluará F
la siguiente función . Fs
Si la función F
regresa , se evaluará {false, Y}
la siguiente función Fs
con argumento . Y
Si la función F
devuelve, R
la función de orden superior or_else/2
devolverá R
. Tenga en cuenta que X
, Y
y R
pueden ser funciones. El ejemplo vuelve false
.
sea dos veces f = f >> f sea más_tres = (+) 3 sea g = dos veces más tres g 7 |> imprimirf "%A" // 13
paquete principal importar "fmt" func dos veces ( f func ( int ) int ) func ( int ) int { retorno func ( x int ) int { retorno f ( f ( x )) } } func main () { plusThree := func ( i int ) int { return i + 3 } g : = dos veces ( más tres ) fmt . Imprimirln ( g ( 7 )) // 13 }
Observe que un literal de función se puede definir con un identificador ( twice
) o de forma anónima (asignado a una variable plusThree
).
dos veces :: ( Int -> Int ) -> ( Int -> Int ) dos veces f = f . F másTres :: Int -> Int másTres = ( + 3 ) principal :: IO () principal = imprimir ( g 7 ) - 13 donde g = dos veces másTres
Explícitamente,
dos veces =. adverbio : 'uu y' más tres =. verbo : 'y + 3' g =. más tres dos veces g 7 13
o tácitamente,
dos veces =. ^: 2 más tres =. +& 3 gramos =. más tres dos veces g 7 13
Usando solo interfaces funcionales:
importar java.util.function.* ; clase Principal { public static void main ( String [] args ) { Función < OperadorIntUnario , OperadorIntUnario > dos veces = f -> f . y entonces ( f ); OperadorIntUnario másTres = i -> i + 3 ; var g = dos veces . aplicar ( másTres ); Sistema . afuera . println ( g . applyAsInt ( 7 )); // 13 } }
O de manera equivalente, con métodos estáticos:
importar java.util.function.* ; clase Principal { OperadorIntUnario estático privado dos veces ( OperadorIntUnario f ) { retorno f . y entonces ( f ); } privado estático int plusThree ( int i ) { return i + 3 ; } public static void main ( String [] args ) { var g = dos veces ( Main :: plusThree ); Sistema . afuera . println ( g . applyAsInt ( 7 )); // 13 } }
Con funciones de flecha:
"uso estricto" ;constante dos veces = f => x => f ( f ( x )); const másTres = i => i + 3 ; const g = dos veces ( másTres ); consola . Iniciar sesión ( g ( 7 )); // 13
O con sintaxis clásica:
"uso estricto" ;función dos veces ( f ) { función de retorno ( x ) { devolución f ( f ( x )); }; } función másTres ( i ) { return i + 3 ; } const g = dos veces ( másTres ); consola . Iniciar sesión ( g ( 7 )); // 13
julia> función dos veces ( f ) resultado de la función ( x ) retorno f ( f ( x )) fin devuelve el resultado final dos veces (función genérica con 1 método) julia> mástres ( i ) = i + 3 mástres (función genérica con 1 método) julia> g = dos veces ( mástres ) (::var"#result#3"{typeof(mástres)}) (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 fun main () { val g = dos veces ( :: másTres ) println ( g ( 7 )) // 13 }
función dos veces ( f ) función de retorno ( x ) retorno f ( f ( x )) fin fin función plusTres ( i ) retorno i + 3 finlocal g = dos veces ( másTres )imprimir ( g ( 7 )) -- 13
resultado de la función = 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 = (+) 3let () = let 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 { función de retorno ( int $x ) uso ( $f ) : int { retorno $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 );$dos veces = 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 que la use
palabra clave haga lo mismo.
utilizar estricto ; utilizar advertencias ; sub dos veces { mi ( $f ) = @_ ; sub { $f -> ( $f -> ( @_ )); }; } sub plusTres { mi ( $i ) = @_ ; $yo + 3 ; } mi $g = dos veces ( \& plusThree ); 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 $plusTres = sub { mi ( $i ) = @_ ; $yo + 3 ; }; mi $g = $dos veces -> ( $plusTres ); imprimir $g -> ( 7 ), "\n" ; # 13
>>> def dos veces ( f ): ... def resultado ( x ): ... devuelve f ( f ( x )) ... devuelve resultado>>> más_tres = lambda i : i + 3>>> g = dos veces ( más_tres ) >>> g ( 7 ) 13
La sintaxis del decorador de Python se usa 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 g
podría implementarse de manera equivalente:
>>> @dos veces ... def g ( i ): ... devolver i + 3>>> g ( 7 ) 13
dos veces <- función ( f ) { retorno ( función ( x ) { f ( f ( x )) }) } plusThree <- función ( i ) { retorno ( i + 3 ) } g <- dos veces ( másTres ) > imprimir ( g ( 7 )) [ 1 ] 13
sub dos veces ( Invocable:D $f ) { return sub { $f ( $f ( $^x )) };}sub plusTres ( Int:D $i ) { return $i + 3 ;}mi $g = dos veces ( &plusTres );digamos $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 alcance 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 pueden asignarse a una variable o invocarse de forma anónima.
def dos veces ( f ) -> ( x ) { f . llamar ( f . llamar ( x )) } fin más_tres = -> ( yo ) { yo + 3 } g = dos veces ( más_tres ) pone g . llamar ( 7 ) # 13
fn dos veces ( f : impl Fn ( i32 ) -> i32 ) -> impl Fn ( i32 ) -> i32 { mover | x | f ( f ( x )) } fn más_tres ( yo : i32 ) -> i32 { yo + 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 ( argumentos : 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 )) ( defina g ( dos veces más tres )) ( pantalla ( g 7 )) ; 13 ( muestra " \n " )
func dos veces ( _ f : @ escapando ( Int ) -> Int ) -> ( Int ) -> Int { return { f ( f ( $0 )) } }let plusThree = { $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 } {return [expr $i + 3 ]}} # resultado: 13 puts [aplicar $dos veces $másTres 7 ]
Tcl usa el comando aplicar 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 permitirEntrada { condición de permiso cualquieraDeCualquier(función [ cadenaEqual ], ciudadanías , Ciudadanos permitidos ) }
La lista de funciones de orden superior en XACML se puede encontrar aquí .
declarar función local:dos veces ( $ f , $ x ) { $ f ( $ f ( $ x )) }; declarar función local: más tres ( $ 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 ) { return x * x ; } cubo doble ( doble x ) { return x * x * x ; } /* Calcula la integral de f() dentro del intervalo [a,b] */ double integral ( double f ( double x ), double a , double b , int n ) { int i ; doble suma = 0 ; doble dt = ( b - a ) / n ; para ( i = 0 ; i < n ; ++ i ) { suma += f ( a + ( i + 0,5 ) * dt ); } devolver suma * dt ; } int main () { printf ( "%g \n " , integral ( cuadrado , 0 , 1 , 100 )); printf ( "%g \n " , integral ( cubo , 0 , 1 , 100 )); devolver 0 ; }
La función qsort de la biblioteca estándar de 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 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 imperativos , es posible lograr algunos de los mismos resultados algorítmicos que se obtienen mediante funciones de orden superior ejecutando código dinámicamente (a veces llamado operaciones Eval u Execute ) en el alcance de la evaluación. Este enfoque puede tener importantes inconvenientes:
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 a menudo conllevan una sobrecarga de tiempo de ejecución adicional en comparación con las funciones puras, y código repetitivo agregado para definir e instanciar un objeto y sus métodos. Los lenguajes que permiten estructuras o objetos basados en pila (en lugar de en montón ) pueden proporcionar más flexibilidad con este método.
Un ejemplo del uso de un registro basado en pila simple en Free Pascal con una función que devuelve una función:
ejemplo de programa ; escriba int = entero ; Txy = registro x , y : int ; fin ; Tf = función ( xy : Txy ) : int ; función f ( xy : Txy ) : int ; comenzar resultado : = xy . y + xy . X ; fin ; función g ( func : Tf ) : Tf ; comenzar resultado : = func ; fin ; var a : Tf ; xy : Txy = ( x : 3 ; y : 7 ) ; comenzar a := g ( @ f ) ; // devolver una función a "a" writeln ( a ( xy )) ; // imprime 10 end .
La función a()
toma un Txy
registro como entrada y devuelve el valor entero de la suma de los campos x
y del registro y
(3 + 7).
La desfuncionalización se puede utilizar para implementar funciones de orden superior en lenguajes que carecen de funciones de primera clase :
// Plantilla de estructuras de datos de funciones desfuncionalizadas < nombre de tipo T > estructura Agregar { valor T ; }; plantilla < nombretipo T > estructura DivBy { valor T ; }; plantilla < nombre de tipo F , nombre de tipo G > estructura Composición { F f ; G g ; }; // Plantilla de implementaciones de aplicaciones de funciones desfuncionalizadas < nombre de tipo F , nombre de tipo G , nombre de tipo X > auto apply ( Composición < F , G > f , X arg ) { return apply ( f . f , apply ( f . g , arg )); } plantilla < nombre de tipo T , nombre de tipo X > aplicación automática ( Agregar < T > f , X arg ) { return arg + f . valor ; } plantilla < nombre de tipo T , nombre de tipo X > aplicación automática ( DivBy < T > f , X arg ) { return arg / f . valor ; } // Plantilla de función de composición de orden superior < nombre de tipo F , nombre de tipo G > Composición < F , G > componer ( 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 se aplica ( f , 9 ); // 7.0f devuelve 0 ; }
En este caso, se utilizan diferentes tipos para activar diferentes funciones mediante la sobrecarga de funciones . La función sobrecargada en este ejemplo tiene la firma auto apply
.