Funktion höherer Ordnung

In Mathematik und Informatik ist eine Funktion höherer Ordnung ( HOF ) eine Funktion , die mindestens eine der folgenden Eigenschaften besitzt:

• nimmt eine oder mehrere Funktionen als Argumente entgegen (d. h. einen prozeduralen Parameter , der ein Parameter einer Prozedur ist , die selbst eine Prozedur ist),
• gibt eine Funktion als Ergebnis zurück.

Alle anderen Funktionen sind Funktionen erster Ordnung . In der Mathematik werden Funktionen höherer Ordnung auch Operatoren oder Funktionale genannt . Der Differentialoperator in der Analysis ist ein gängiges Beispiel, da er eine Funktion auf ihre Ableitung abbildet , die ebenfalls eine Funktion ist. Funktionen höherer Ordnung sollten nicht mit anderen Bedeutungen des Begriffs „Funktor“ in der Mathematik verwechselt werden (siehe Funktor (Begriffsklärung)) .

Im ungetypten Lambda-Kalkül sind alle Funktionen von höherer Ordnung; in einem getypten Lambda-Kalkül , von dem die meisten funktionalen Programmiersprachen abgeleitet sind, sind Funktionen höherer Ordnung, die eine Funktion als Argument nehmen, Werte mit Typen der Form . ${\displaystyle (\tau _{1}\to \tau _{2})\to \tau _{3}}$

• Die `map`- Funktion, die in vielen funktionalen Programmiersprachen vorkommt, ist ein Beispiel für eine Funktion höherer Ordnung. Sie nimmt eine Funktion ` f` und eine Sammlung von Elementen als Argumente entgegen und gibt als Ergebnis eine neue Sammlung zurück, in der `f` auf jedes Element der Sammlung angewendet wird.
• Die Sortierfunktion akzeptiert eine Vergleichsfunktion als Parameter und ermöglicht es dem Programmierer , den Sortieralgorithmus von den Vergleichen der zu sortierenden Elemente zu trennen. DieStandardfunktion in C ist ein Beispiel dafür.qsort
• Eine Filterfunktion , die eine Sammlung und eine Funktion entgegennimmt, die wahr oder falsch zurückgibt, und eine neue Sammlung zurückgibt, die die Elemente der Parametersammlung enthält, für die die Funktion wahr zurückgegeben hat.
• fold (einschließlich foldl und foldr )
• Scan
• anwenden
• Funktionszusammensetzung
• Integration
• Rückruf
• Baumdurchquerung
• Die Montague-Grammatik , eine semantische Theorie der natürlichen Sprache, verwendet Funktionen höherer Ordnung.

Die Beispiele sollen nicht dazu dienen, Programmiersprachen zu vergleichen und gegenüberzustellen, sondern als Beispiele für die Syntax von Funktionen höherer Ordnung zu dienen.

In den folgenden Beispielen nimmt die Funktion höherer Ordnung twiceeine Funktion entgegen und wendet diese zweimal auf einen Wert an. Falls twicesie mehrmals auf denselben Wert angewendet werden muss, fsollte sie vorzugsweise eine Funktion anstelle eines Wertes zurückgeben. Dies entspricht dem Prinzip „ Wiederhole dich nicht “.

zweimal ← { ⍺⍺ ⍺⍺ ⍵ }plusthree ← { ⍵ + 3 }g ← { plusthree twice ⍵ } g 7 13

Oder auf stillschweigende Weise:

zweimal ← ⍣ 2plusthree ← + ∘ 3g ← plus drei zweimal g 7 13

Verwendung std::functionin C++11 :

import std ;auto twice = []( const std :: function < int ( int ) >& f ) -> auto { return [ f ]( int x ) -> int { return f ( f ( x )); }; };auto plusThree = []( int i ) -> int { return i + 3 ; };int main () { auto g = twice ( plusThree );std :: println ( "{}" , g ( 7 )); // 13 }

Oder, mit den von C++14 bereitgestellten generischen Lambdas:

import std ;auto twice = []( const auto & f ) -> auto { return [ f ]( int x ) -> int { return f ( f ( x )); }; };auto plusThree = []( int i ) -> int { return i + 3 ; };int main () { auto g = twice ( plusThree );std :: println ( "{}" , g ( 7 )); // 13 }

Nur mit Delegaten:

using System ;public class Program { public static void Main ( string [] args ) { Func < Func < int , int > , Func < int , int >> twice = f => x => f ( f ( x ));Func < int , int > plusThree = i => i + 3 ;var g = twice ( plusThree );Console.WriteLine ( g ( 7 ) ); // 13 } }

Oder gleichwertig mit statischen Methoden:

using System ;public class Program { private static Func < int , int > Twice ( Func < int , int > f ) { return x => f ( f ( x )); }private static int PlusThree ( int i ) => i + 3 ;public static void Main ( string [] args ) { var g = Twice ( PlusThree );Console.WriteLine ( g ( 7 ) ); // 13 } }

( defn twice [ f ] ( fn [ x ] ( f ( f x ))))( defn plus-three [ i ] ( + i 3 ))( def g ( zweimal plus drei ))( println ( g 7 )) ; 13

twice = function ( f ) { return function ( x ) { return f ( f ( x )); }; };plusThree = function ( i ) { return i + 3 ; };g = zweimal ( plus Drei );writeOutput ( g ( 7 )); // 13

( defun twice ( f ) ( lambda ( x ) ( funcall f ( funcall f x )))) ( defun plus-three ( i ) ( + i 3 )) ( defvar g ( twice #' plus-three )) ( print ( funcall g 7 ))

import std.stdio : writeln ;​​alias twice = ( f ) => ( int x ) => f ( f ( x ));alias plusThree = ( int i ) => i + 3 ;void main () { auto g = twice ( plusThree );writeln ( g ( 7 )); // 13 }

int Function ( int ) twice ( int Function ( int ) f ) { return ( x ) { return f ( f ( x )); }; }int plusThree ( int i ) { return i + 3 ; }void main () { final g = twice ( plusThree ); print ( g ( 7 )); // 13 }

In Elixir können Sie Moduldefinitionen und anonyme Funktionen mischen.

defmodule Hof do def twice ( f ) do fn ( x ) -> f . ( f . ( x )) end end endplus_three = fn ( i ) -> i + 3 endg = Hof . twice ( plus_three )IO . puts g . ( 7 ) # 13

Alternativ können wir auch mit rein anonymen Funktionen komponieren.

zweimal = fn ( f ) -> fn ( x ) -> f . ( f . ( x )) Ende Endeplus_three = fn ( i ) -> i + 3 endg = zweimal . ( plus_drei )IO . puts g . ( 7 ) # 13

or_else ([], _) -> false ; or_else ([ F | Fs ], X ) -> or_else ( Fs , X , F ( X )).or_else ( Fs , X , false ) -> or_else ( Fs , X ); or_else ( Fs , _, { false , Y }) -> or_else ( Fs , Y ); or_else (_, _, R ) -> R .or_else ([ fun erlang : is_integer / 1 , fun erlang : is_atom / 1 , fun erlang : is_list / 1 ], 3 . 23 ).

In diesem Erlang-Beispiel nimmt die Funktion höherer Ordnung or_else/2eine Liste von Funktionen Fsund ein Argument entgegen X. Sie wertet die Funktion Fmit dem Argument Xals Argument aus. Gibt die Funktion `false` zurück, wird Fdie nächste Funktion in ` list` ausgewertet. Gibt die Funktion `false` zurück, wird die nächste Funktion in `list` mit dem Argument `false` ausgewertet. Gibt die Funktion ` false` zurück, gibt die Funktion höherer Ordnung ` false` zurück . Beachten Sie, dass `false`, `false` und `false` Funktionen sein können. Das Beispiel gibt `false` zurück . FsF{false, Y}FsYFRor_else/2RXYRfalse

zweimal f = f >> f​sei plus_three = (+) 3sei g = zweimal plus dreig 7 |> printf "%A" // 13

Hauptpaket​import "fmt"func twice ( 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 := zweimal ( plus Drei )fmt.Println ( g ( 7 ) ) // 13 }

Beachten Sie, dass ein Funktionsliteral entweder mit einem Bezeichner ( twice) oder anonym (der Variablen zugewiesen plusThree) definiert werden kann.

def twice = { f , x -> f ( f ( x )) } def plusThree = { it + 3 } def g = twice . curry ( plusThree ) println g ( 7 ) // 13

zweimal :: ( Int -> Int ) -> ( Int -> Int ) zweimal f = f . fplusThree :: Int -> Int plusThree = ( + 3 )main :: IO () main = print ( g 7 ) -- 13 wobei g = zweimal plus Drei

Ausdrücklich,

zweimal = Adverb : 'uu y'plusthree =. Verb : 'y + 3' g =. plusthree zweimal g 7 13

oder stillschweigend

zweimal =. ^: 2plusdrei =. +& 3 g =. plusdrei zweimal g 7 13

Verwendung ausschließlich funktionaler Schnittstellen:

import java.util.function.* ;class Main { public static void main ( String [] args ) { Function < IntUnaryOperator , IntUnaryOperator > twice = f -> f . andThen ( f );IntUnaryOperator plusThree = i -> i + 3 ;var g = twice . apply ( plusThree );System.out.println ( g.applyAsInt ( 7 ) ) ; // 13 } }​​​

Oder gleichwertig mit statischen Methoden:

import java.util.function.* ;class Main { private static IntUnaryOperator twice ( IntUnaryOperator f ) { return f . andThen ( f ); }private static int plusThree ( int i ) { return i + 3 ; }public static void main ( String [] args ) { var g = twice ( Main :: plusThree );System.out.println ( g.applyAsInt ( 7 ) ) ; // 13 } }​​​

Mit Pfeilfunktionen:

"use strict" ;const twice = f => x => f ( f ( x ));const plusThree = i => i + 3 ;const g = twice ( plusThree );console.log ( g ( 7 ) ) ; // 13

Oder mit klassischer Syntax:

"use strict" ;function twice ( f ) { return function ( x ) { return f ( f ( x )); }; }function plusThree ( i ) { return i + 3 ; }const g = twice ( plusThree );console.log ( g ( 7 ) ) ; // 13

julia> function twice ( f ) function result ( x ) return f ( f ( x )) end return result end twice (generische Funktion mit 1 Methode)julia> plusthree ( i ) = i + 3 plusthree (generische Funktion mit 1 Methode)julia> g = twice ( plusthree ) (::var"#result#3"{typeof(plusthree)}) (generische Funktion mit 1 Methode)julia> g ( 7 ) 13

fun twice ( f : ( Int ) -> Int ): ( Int ) -> Int { return { f ( f ( it )) } }fun plusThree ( i : Int ) = i + 3fun main () { val g = twice ( :: plusThree )println ( g ( 7 )) // 13 }

function twice ( f ) return function ( x ) return f ( f ( x )) end endfunction plusThree ( i ) return i + 3 endlokales g = zweimal ( plus Drei )print ( g ( 7 )) -- 13

function result = twice ( f ) result = @( x ) f ( f ( x )); endplusthree = @( i ) i + 3 ;g = zweimal ( plus drei )disp ( g ( 7 )); % 13

sei zweimal f x = f ( f x )sei plus_three = (+) 3let () = let g = zweimal plus_drei inprint_int ( g 7 ); (* 13 *) print_newline ()

<?phpdeclare ( strict_types = 1 );function twice ( callable $f ) : Closure { return function ( int $x ) use ( $f ) : int { return $f ( $f ( $x )); }; }function plusThree ( int $i ) : int { return $i + 3 ; }$g = twice ( 'plusThree' );echo $g ( 7 ), " \n " ; // 13

oder mit allen Funktionen in Variablen:

<?phpdeclare ( strict_types = 1 );$twice = fn ( callable $f ) : Closure => fn ( int $x ) : int => $f ( $f ( $x ));$plusThree = fn ( int $i ) : int => $i + 3 ;$g = $twice ( $plusThree );echo $g ( 7 ), " \n " ; // 13

Beachten Sie, dass Pfeilfunktionen implizit alle Variablen erfassen, die aus dem übergeordneten Gültigkeitsbereich stammen, ^{[ 1 ]} während anonyme Funktionen das useSchlüsselwort benötigen, um dasselbe zu tun.

use strict ; use warnings ;sub twice { my ( $f ) = @_ ; sub { $f -> ( $f -> ( @_ )); }; }sub plusThree { my ( $i ) = @_ ; $i + 3 ; }my $g = twice ( \& plusThree );print $g -> ( 7 ), "\n" ; # 13

oder mit allen Funktionen in Variablen:

use strict ; use warnings ;my $twice = sub { my ( $f ) = @_ ; sub { $f -> ( $f -> ( @_ )); }; };my $plusThree = sub { my ( $i ) = @_ ; $i + 3 ; };my $g = $twice -> ( $plusThree );print $g -> ( 7 ), "\n" ; # 13

def twice ( f : Callable [ Any ]) -> Any : def result ( x : Any ) -> Any : return f ( f ( x )) return resultplus_three : Callable [ int ] = lambda i : i + 3g : int = twice ( plus_three )print ( g ( 7 )) # gibt 13 aus

Die Python-Dekorator-Syntax wird häufig verwendet, um eine Funktion durch das Ergebnis der Übergabe dieser Funktion an eine Funktion höherer Ordnung zu ersetzen. Zum Beispiel gkönnte die Funktion äquivalent implementiert werden:

@twice def g ( i : int ) -> int : return i + 3print ( g ( 7 )) # gibt 13 aus

zweimal <- \ ( f ) \ ( x ) f ( f ( x ))plusThree <- function ( i ) i + 3g <- twice ( plusThree )> g ( 7 ) [ 1 ] 13

sub twice ( Callable:D $f ) { return sub { $f ( $f ( $^x )) }; } sub plusThree ( Int:D $i ) { return $i + 3 ; } my $g = twice ( &plusThree ); say $g ( 7 ); # 13

In Raku sind alle Codeobjekte Closures und können daher von einem äußeren Gültigkeitsbereich aus auf innere „lexikalische“ Variablen zugreifen, da die lexikalische Variable innerhalb der Funktion „geschlossen“ ist. Raku unterstützt außerdem die „Pointy-Block“-Syntax für Lambda-Ausdrücke, die einer Variablen zugewiesen oder anonym aufgerufen werden können.

def twice ( f ) - > ( x ) { f.call ( f.call ( x ) ) } end​​plus_three = -> ( i ) { i + 3 }g = zweimal ( plus_drei )puts g . call ( 7 ) # 13

fn twice ( f : impl Fn ( i32 ) -> i32 ) -> impl Fn ( i32 ) -> i32 { move | x | f ( f ( x )) }fn plus_three ( i : i32 ) -> i32 { i + 3 }fn main () { let g = twice ( plus_three );println! ( "{}" , g ( 7 )) // 13 }

object Main { def twice ( f : Int => Int ): Int => Int = f compose fdef plusThree ( i : Int ): Int = i + 3def main ( args : Array [ String ]): Unit = { val g = twice ( plusThree )print ( g ( 7 )) // 13 } }

( define ( compose f g ) ( lambda ( x ) ( f ( g x ))))( define ( twice f ) ( compose f f ))( define ( plus-three i ) ( + i 3 ))( define g ( zweimal plus drei ))( display ( g 7 )) ; 13 ( display " \n " )

func twice ( _ f : @ escaping ( Int ) -> Int ) -> ( Int ) -> Int { return { f ( f ( $0 )) } }let plusThree = { $0 + 3 }sei g = zweimal ( plus Drei )print ( g ( 7 )) // 13

set twice {{ f x } {apply $f [apply $f $x ]}} set plusThree {{ i } {return [expr $i + 3 ]}}# Ergebnis: 13 puts [apply $twice $plusThree 7 ]

Tcl verwendet den apply-Befehl, um eine anonyme Funktion anzuwenden (seit Version 8.6).

Der XACML-Standard definiert Funktionen höherer Ordnung, um eine Funktion auf mehrere Werte von Attributgruppen anzuwenden.

rule allowEntry { permit condition anyOfAny(function [ stringEqual ], citizenships , allowedCitizenships ) }

Die Liste der Funktionen höherer Ordnung in XACML finden Sie hier .

declare function local:twice ( $ f , $ x ) { $ f ( $ f ( $ x )) };declare function local:plusthree ( $ i ) { $ i + 3 };local:twice ( local:plusthree # 1 , 7 ) (: 13 :)

Funktionszeiger in Sprachen wie C , C++ , Fortran und Pascal ermöglichen es Programmierern, Referenzen auf Funktionen weiterzugeben. Der folgende C-Code berechnet eine Näherung des Integrals einer beliebigen Funktion:

#include <stdio.h>double square ( double x ) { return x * x ; }double cube ( double x ) { return x * x * x ; }/* Berechne das Integral von f() im Intervall [a,b] */ double integral ( double f ( double x ), double a , double b , int n ) { int i ; double sum = 0 ; double dt = ( b - a ) / n ; for ( i = 0 ; i < n ; ++ i ) { sum += f ( a + ( i + 0.5 ) * dt ); } return sum * dt ; }int main () { printf ( "%g \n " , integral ( square , 0 , 1 , 100 )); printf ( "%g \n " , integral ( cube , 0 , 1 , 100 )); return 0 ; }

Die qsort- Funktion aus der C-Standardbibliothek verwendet einen Funktionszeiger, um das Verhalten einer Funktion höherer Ordnung zu emulieren.

Makros können auch verwendet werden, um einige Effekte von Funktionen höherer Ordnung zu erzielen. Allerdings lässt sich das Problem der Variablenübernahme mit Makros nicht ohne Weiteres vermeiden; zudem können sie zu großen Mengen an dupliziertem Code führen, was die Optimierung durch einen Compiler erschwert. Makros sind im Allgemeinen nicht stark typisiert, obwohl sie stark typisierten Code erzeugen können.

In anderen imperativen Programmiersprachen lassen sich ähnliche algorithmische Ergebnisse wie mit Funktionen höherer Ordnung erzielen, indem Code dynamisch im Auswertungsbereich ausgeführt wird (manchmal auch Eval- oder Execute- Operationen genannt). Dieser Ansatz kann jedoch erhebliche Nachteile mit sich bringen:

• The argument code to be executed is usually not statically typed; these languages generally rely on dynamic typing to determine the well-formedness and safety of the code to be executed.
• The argument is usually provided as a string, the value of which may not be known until run-time. This string must either be compiled during program execution (using just-in-time compilation) or evaluated by interpretation, causing some added overhead at run-time, and usually generating less efficient code.

In object-oriented programming languages that do not support higher-order functions, objects can be an effective substitute. An object's methods act in essence like functions, and a method may accept objects as parameters and produce objects as return values. Objects often carry added run-time overhead compared to pure functions, however, and added boilerplate code for defining and instantiating an object and its method(s). Languages that permit stack-based (versus heap-based) objects or structs can provide more flexibility with this method.

An example of using a simple stack based record in Free Pascal with a function that returns a function:

programexample;typeint=integer;Txy=recordx,y:int;end;Tf=function(xy:Txy):int;functionf(xy:Txy):int;beginResult:=xy.y+xy.x;end;functiong(func:Tf):Tf;beginresult:=func;end;vara:Tf;xy:Txy=(x:3;y:7);begin a := g ( @ f ) ; // gibt eine Funktion an "a" zurück writeln ( a ( xy )) ; // gibt 10 aus end .

Die Funktion a()nimmt einen TxyDatensatz als Eingabe und gibt den ganzzahligen Wert der Summe der Felder des Datensatzes x( y3 + 7) zurück.

Defunktionalisierung kann verwendet werden, um Funktionen höherer Ordnung in Sprachen zu implementieren, denen Funktionen erster Klasse fehlen :

// Defunktionalisierte Funktionsdatenstrukturen template < typename T > struct Add { T value ; }; template < typename T > struct DivBy { T value ; }; template < typename F , typename G > struct Composition { F f ; G g ; };// Defunktionalisierte Funktionsanwendungsimplementierungen 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 > auto apply ( Add < T > f , X arg ) { return arg + f . value ; }template < typename T , typename X > auto apply ( DivBy < T > f , X arg ) { return arg / f . value ; }// Höherwertige Kompositionsfunktion template < 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 }, Add <int> { 5 } ); apply ( f , 3 ); // 4.0f apply ( f , 9 ); // 7.0f return 0 ; }

In diesem Fall werden unterschiedliche Datentypen verwendet, um über Funktionsüberladung verschiedene Funktionen auszulösen . Die überladene Funktion in diesem Beispiel hat die folgende Signatur auto apply:

• Funktion erster Klasse
• Kombinatorische Logik
• Funktionsprogrammierung
• Funktionale Programmierung
• Kappa-Kalkül – ein Formalismus für Funktionen, der Funktionen höherer Ordnung ausschließt
• Strategiemuster
• Nachrichten höherer Ordnung