En matemáticas e informática , una función de orden superior es una función que realiza al menos una de las siguientes acciones:
- toma una o más funciones como argumentos (es decir , parámetros de procedimiento ),
- devuelve una función como 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 , 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.
Ejemplos generales
map
función, que se encuentra 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 clasificación, que toman una función de comparación como parámetro, lo que permite al programador separar el algoritmo de clasificación de las comparaciones de los elementos que se clasifican. La función estándar C es un ejemplo de esto.
qsort
- filtrar
- pliegue
- solicitar
- Composición de funciones
- Integración
- Llamar de vuelta
- Cruce de árboles
- La gramática de Montague , una teoría semántica del lenguaje natural, usa funciones de orden superior
Soporte en lenguajes de programación
Apoyo directo
Los ejemplos no están destinados a comparar y contrastar lenguajes de programación, sino a 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 aplica la función a algún valor dos veces. Si twice
tiene que aplicarse varias veces para el mismo f
, preferiblemente debe devolver una función en lugar de un valor. Esto está en consonancia con el principio de " no repetir ".
APL
dos veces ← { ⍺⍺ ⍺⍺ ⍵ } más tres ← { ⍵ + 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
C ++
Utilizando std::function
en C ++ 11:
#include #include auto dos veces = [] ( const std :: function < int ( int ) > & f ) { return [ & f ] ( int x ) { return f ( f ( x )); }; };auto plus_three = [] ( 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:
#include auto dos veces = [] ( const auto & f ) { return [ & f ] ( int x ) { return f ( f ( x )); }; };auto plus_three = [] ( int i ) { return i + 3 ; };int main () { auto g = dos veces ( más_tres ); std :: cout << g ( 7 ) << '\ n' ; // 13 }
C#
Usando solo delegados:
usando el sistema ; Programa de clase pública { public static void Main ( string [] args ) { Func < Func < int , int >, Func < int , int >> two = f => x => f ( f ( x )); Func < int , int > másTres = i => i + 3 ; var g = dos veces (más tres ); Consola . WriteLine ( g ( 7 )); // 13 } }
O de manera equivalente, con métodos estáticos:
usando el sistema ; Programa de clase pública { Func estática privada < 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 } }
Clojure
( 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
Lenguaje de marcado ColdFusion (CFML)
dos veces = función ( f ) { función de retorno ( x ) { retorno f ( f ( x )); }; }; másTres = función ( i ) { return i + 3 ; };g = dos veces (más tres );escribirOutput ( g ( 7 )); // 13
D
import 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 ); escrito ( g ( 7 )); // 13 }
Elixir
En Elixir, puede mezclar definiciones de módulos y funciones anónimas
defmodule Hof hacer def dos veces ( f ) hacer fn ( x ) -> f . ( f . ( x )) fin fin finmás_tres = fn ( i ) -> 3 + i finalg = Hof . dos veces ( más_tres )IO . pone g . ( 7 ) N.º 13
Alternativamente, también podemos componer usando funciones anónimas puras.
dos veces = fn ( f ) -> fn ( x ) -> f . ( f . ( x )) fin finmás_tres = fn ( i ) -> 3 + i finalg = dos veces . ( más_tres )IO . pone g . ( 7 ) N.º 13
Erlang
o bien ([], _) -> falso ; o_else ([ F | Fs ], X ) -> o_else ( Fs , X , F ( X )).o_else ( Fs , X , falso ) -> o_else ( Fs , X ); o_else ( Fs , _, { falso , Y }) -> o_else ( Fs , Y ); or_else (_, _, R ) -> R .or_else ([ diversión erlang : is_integer / 1 , diversión erlang : is_atom / 1 , diversión erlang : 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 F
devuelve falso Fs
, se evaluará la siguiente función . Si la función F
regresa , se evaluará {false, Y}
la siguiente función Fs
con argumento Y
. Si la función F
retorna R
la función de orden superior or_else/2
devolverá R
. Tenga en cuenta que X
, Y
y R
pueden ser funciones. Vuelve el ejemplo false
.
F#
sea dos veces f = f >> fsea más_tres = (+) 3sea g = dos veces más_tresg 7 |> printf "% A" // 13
Ir
paquete principalimportar "fmt"func dos veces ( f func ( int ) int ) func ( int ) int { return func ( x int ) int { return f ( f ( x )) } }func main () { másTres : = func ( i int ) int { return i + 3 }g : = dos veces (más tres )fmt . Println ( g ( 7 )) // 13 }
Observe que una función literal se puede definir con un identificador ( twice
) o de forma anónima (asignada a una variable plusThree
).
Haskell
dos veces :: ( Int -> Int ) -> ( Int -> Int ) dos veces f = f . FmásTres :: Int -> Int másTres = ( + 3 )main :: IO () main = print ( g 7 ) - 13 donde g = dos veces másTres
J
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 =. + Y 3 g =. más tres dos veces g 7 13
Java (1.8+)
Usando solo interfaces funcionales:
importar java.util.function. * ;class Main { public static void main ( String [] args ) { Función < IntUnaryOperator , IntUnaryOperator > dos veces = f -> f . y luego ( f ); IntUnaryOperator plusThree = i -> i + 3 ; var g = dos veces . aplicar ( másTres ); Sistema . fuera . println ( g . applyAsInt ( 7 )); // 13 } }
O de manera equivalente, con métodos estáticos:
importar java.util.function. * ;la clase principal { privada estática IntUnaryOperator dos veces ( IntUnaryOperator f ) { retorno f . y luego ( f ); } private static int plusThree ( int i ) { return i + 3 ; } public static void main ( String [] args ) { var g = dos veces ( Main :: plusThree ); Sistema . fuera . println ( g . applyAsInt ( 7 )); // 13 } }
JavaScript
"uso estricto" ;constante dos veces = f => x => f ( f ( x ));const másTres = i => i + 3 ;const g = dos veces (más tres );consola . log ( g ( 7 )); // 13
Julia
julia> función dos veces ( f ) función resultado ( x ) devolver f ( f ( x )) fin devolver resultado final 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 = twice ( plusthree ) (:: var "# result # 3" {typeof (plusthree)}) (función genérica con 1 método)julia> g ( 7 ) 13
Kotlin
diversión dos veces ( f : ( Int ) -> Int ): ( Int ) -> Int { return { f ( f ( it )) } }diversión másTres ( i : Int ) = i + 3fun main () { val g = dos veces ( :: másTres ) println ( g ( 7 )) // 13 }
Lua
función local dos veces ( f ) función de retorno ( x ) retorno f ( f ( x )) fin fin función local plusThree ( i ) return i + 3 endlocal g = dos veces (más tres )impresión ( g ( 7 )) - 13
MATLAB
resultado de la función = dos veces ( f ) resultado = @ interior función val = interior ( x ) val = f ( f ( x )); finalfinalmás tres = @ ( i ) i + 3 ; g = dos veces (más tres ) disp ( g ( 7 )); % 13
OCaml
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 ()
PHP
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ás tres' );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ás tres );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.
Pascal
{$ mode objfpc}type fun = function ( x : Integer ) : Integer ;función dos veces ( f : diversión ; x : entero ) : entero ;empezar resultado : = f ( f ( x )) ;terminar ;función másTres ( i : Entero ) : Entero ;empezar resultado : = i + 3 ;terminar ;empezar Writeln ( dos veces ( @ plusThree , 7 )) ; {13}fin .
Perl
uso estricto ; use advertencias ;sub dos veces { mi ( $ f ) = @_ ; sub { $ f -> ( $ f -> ( @_ )); }; }sub plusThree { mi ( $ i ) = @_ ; $ i + 3 ; }my $ g = dos veces ( \ & plusThree );imprimir $ g -> ( 7 ), "\ n" ; # 13
o con todas las funciones en variables:
uso estricto ; use advertencias ;mi $ dos veces = sub { mi ( $ f ) = @_ ; sub { $ f -> ( $ f -> ( @_ )); }; };my $ plusThree = sub { my ( $ x ) = @_ ; $ x + 3 ; };my $ g = $ dos veces -> ( $ plusThree );imprimir $ g -> ( 7 ), "\ n" ; # 13
Pitón
>>> def dos veces ( f ): ... def resultado ( x ): ... devuelve f ( f ( x )) ... devuelve el 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:
>>> @twice ... def g ( i ): ... return i + 3>>> g ( 7 ) 13
R
dos veces <- función ( f ) { retorno ( función ( x ) { f ( f ( x )) }) }másTres <- función ( i ) { return ( i + 3 ) }g <- dos veces (más tres )> imprimir ( g ( 7 )) [ 1 ] 13
Raku
sub dos veces ( Invocable: D $ f ) { return sub { $ f ( $ f ( $ ^ x ))};}sub plusThree ( Int: D $ i ) { return $ i + 3 ;}my $ g = dos veces ( & plusThree );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 á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.
Rubí
def dos veces ( f ) -> ( x ) { f . llamar f . llamar ( x ) } finalizarmás_tres = -> ( i ) { i + 3 }g = dos veces ( más_tres )pone g . llamar ( 7 ) # 13
Oxido
fn dos veces ( f : impl Fn ( i32 ) -> i32 ) -> impl Fn ( i32 ) -> i32 { mover | x | f ( f ( x )) }fn más_tres ( i : i32 ) -> i32 { yo + 3 }fn main () { sea g = dos veces ( más_tres ); println! ( "{}" , g ( 7 )) // 13 }
Scala
objeto Principal { def dos veces ( f : Int => Int ) : Int => Int = f componer f def másTres ( i : Int ) : Int = i + 3 def main ( args : Array [ String ]) : Unidad = { val g = dos veces ( másTres ) imprimir ( g ( 7 )) // 13 } }
Esquema
( definir ( agregar x y ) ( + x y )) ( definir ( f x ) ( lambda ( y ) ( + x y ))) ( mostrar (( f 3 ) 7 )) ( mostrar ( agregar 3 7 ))
En este ejemplo de esquema, la función de orden superior (f x)
se utiliza para implementar el curado . Toma un solo argumento y devuelve una función. La evaluación de la expresión ((f 3) 7)
primero devuelve una función después de evaluar (f 3)
. La función devuelta es (lambda (y) (+ 3 y))
. Luego, evalúa la función devuelta con 7 como argumento, devolviendo 10. Esto es equivalente a la expresión (add 3 7)
, ya que (f x)
es equivalente a la forma curry de (add x y)
.
Rápido
func dos veces ( _ f : @ escapar ( Int ) -> Int ) -> ( Int ) -> Int { return { f ( f ( $ 0 )) } }let plusThree = { $ 0 + 3 }sea g = dos veces (más tres )imprimir ( g ( 7 )) // 13
Tcl
establecer dos veces {{ f x } {aplicar $ f [aplicar $ f $ x ]}} establecer másTres {{ i } {devolver [expr $ i + 3 ]}}Resultados: # 13 pone [aplican $ dos veces $ plusThree 7 ]
Tcl usa el comando apply para aplicar una función anónima (desde 8.6).
XACML
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.
rule allowEntry { permiso condición anyOfAny (función [ stringEqual ], ciudadanías , permitidas ciudadanías ) }
La lista de funciones de orden superior en XACML se puede encontrar aquí .
XQuery
declarar la función local: dos veces ( $ f , $ x ) { $ f ( $ f ( $ x )) };declarar función local: plusthree ( $ i ) { $ i + 3 };local: dos veces ( local: más tres # 1 , 7 ) (: 13 :)
Alternativas
Punteros de función
Los punteros de función en lenguajes como C y C ++ 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:
#include doble cuadrado ( doble x ) { return x * x ; } cubo doble ( doble x ) { retorno x * x * x ; }/ * Calcular la integral de f () en el intervalo [a, b] * / doble integral ( doble f ( doble x ), doble un , doble 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 ); } devuelve 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 de C usa un puntero de función para emular el comportamiento de una función de orden superior.
Macros
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 resultar en grandes cantidades de código duplicado, lo que puede ser más difícil de optimizar para un compilador. Por lo general, las macros no están fuertemente tipadas, aunque pueden producir código fuertemente tipado.
Evaluación de código dinámico
En otros lenguajes de programación imperativos , 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 llamado operaciones Eval o Ejecutar ) en el alcance de la evaluación. Puede haber importantes inconvenientes en este enfoque:
- El código de argumento que se ejecutará normalmente no se escribe estáticamente ; estos lenguajes generalmente se basan en la escritura dinámica para determinar el buen formato y la seguridad del código que se va a ejecutar.
- El argumento generalmente se proporciona como una cadena, cuyo valor puede no conocerse hasta el tiempo de ejecución. Esta cadena debe compilarse durante la ejecución del programa (utilizando la compilación justo a tiempo ) o evaluarse mediante interpretación , lo que genera una sobrecarga adicional en tiempo de ejecución y, por lo general, genera un código menos eficiente.
Objetos
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 un código repetitivo agregado para definir y crear instancias de un objeto y su (s) método (s). Los lenguajes que permiten estructuras o objetos basados en pilas (en lugar de en pilas ) pueden proporcionar más flexibilidad con este método.
Un ejemplo del uso de un registro basado en una pila simple en Free Pascal con una función que devuelve una función:
ejemplo de programa ;tipo int = entero ; Txy = registro x , y : int ; terminar ; Tf = función ( xy : Txy ) : int ; función f ( xy : Txy ) : int ; comenzar Resultado : = xy . y + xy . x ; terminar ;función g ( func : Tf ) : Tf ; comenzar resultado : = func ; terminar ;var a : Tf ; xy : Txy = ( x : 3 ; y : 7 ) ;comenzar a : = g ( @ f ) ; // devuelve una función a "a" writeln ( a ( xy )) ; // imprime 10 finales .
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).
Desfuncionalización
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 función desfuncionalizada < typename T > struct Add { T value ; }; plantilla < typename T > struct DivBy { T valor ; }; plantilla < typename F , typename G > struct Composition { F f ; G g ; };// Plantilla de implementaciones de aplicación de función desfuncionalizada < typename F , typename G , typename X > auto aplicar ( Composición < 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 ) { return arg + f . valor ; } plantilla < typename T , typename X > aplicar automáticamente ( DivBy < T > f , X arg ) { return 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 Composition < F , G > { f , g }; }int main ( int argc , const char * argv []) { auto f = compose ( DivBy < float > { 2.0f }, Add < int > { 5 }); aplicar ( f , 3 ); // 4.0f aplicar ( f , 9 ); // 7.0f return 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
.
Ver también
- 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
Referencias
- ^ "PHP: Funciones de flecha - Manual" . www.php.net . Consultado el 1 de marzo de 2021 .