Funkce vyššího řádu - Higher-order function - Wikipedia

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (září 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v matematika a počítačová věda, a funkce vyššího řádu je funkce který provádí alespoň jednu z následujících akcí:

• bere jednu nebo více funkcí jako argumenty (tj. procedurální parametry ),
• jako výsledek vrátí funkci.

Všechny ostatní funkce jsou funkce prvního řádu. V matematice se také nazývají funkce vyššího řádu operátory nebo funkcionáři. The operátor diferenciálu v počet je běžným příkladem, protože mapuje funkci na svoji derivát, také funkce. Funkce vyššího řádu by neměly být zaměňovány s jinými použitími slova „funktor“ v celé matematice, viz Funktor (disambiguation).

V netypickém lambda kalkul, všechny funkce jsou vyššího řádu; v zadaný lambda kalkul, z nichž většina Funkcionální programování jazyky jsou odvozeny, funkce vyššího řádu, které berou jednu funkci jako argument, jsou hodnoty s typy formuláře ${ displaystyle ( tau _ {1} to tau _ {2}) to tau _ {3}}$.

Obecné příklady

• mapa Funkce nalezená v mnoha funkčních programovacích jazycích je jedním příkladem funkce vyššího řádu. Bere jako argumenty funkci F a kolekce prvků a jako výsledek vrátí novou kolekci s F aplikován na každý prvek ze sbírky.
• Třídicí funkce, které berou srovnávací funkci jako parametr, což umožňuje programátorovi oddělit třídicí algoritmus od porovnání seřazovaných položek. The C Standard funkce qsort je toho příkladem.
• filtr
• složit
• aplikovat
• Složení funkce
• Integrace
• Zpětné volání
• Traverz stromu
• Montague gramatika, sémantická teorie přirozeného jazyka, používá funkce vyššího řádu

Podpora v programovacích jazycích

Bylo navrženo, aby tento článek byl rozdělit do nového článku s názvem Porovnání programovacích jazyků (funkce vyššího řádu). (Diskutujte) (Květen 2016)

Přímá podpora

Tyto příklady nejsou určeny k porovnání a kontrastu programovacích jazyků, ale slouží jako příklady syntaxe funkcí vyššího řádu

V následujících příkladech funkce vyššího řádu dvakrát vezme funkci a použije funkci na nějakou hodnotu dvakrát. Li dvakrát musí být pro stejný použit několikrát F pokud možno by měl vrátit funkci spíše než hodnotu. To je v souladu s „neopakuj se " zásada.

OCAML

Výslovně

nechat přidat3 X = X + 3nechat dvakrát F X = F (F X)print_int (dvakrát přidat3 7) (* 13 *)

Jednořádkový

print_int ((zábava F X -> F (F X)) ((+)3) 7) (* 13 *)

APL

      dvakrát←{⍺⍺ ⍺⍺ ⍵}      plus tři←{⍵+3}      G←{plus tři dvakrát ⍵}          G 713

Nebo tichým způsobem:

      dvakrát←⍣2      plus tři←+∘3      G←plus tři dvakrát          G 713

J

Výslovně,

   dvakrát=.     příslovce : 'u u y'   plus tři=. sloveso   : 'y + 3'      G=. plus tři dvakrát      G 713

nebo mlčky,

   dvakrát=. ^:2   plus tři=. +&3      G=. plus tři dvakrát      G 713

nebo point-free styl,

   +&3(^:2) 713

Krajta

>>> def dvakrát(F):...     def výsledek(A):...         vrátit se F(F(A))...     vrátit se výsledek>>> plus tři = lambda X: X + 3>>> G = dvakrát(plus tři)>>> G(7)13

Syntaxe dekorátoru Pythonu se často používá k nahrazení funkce výsledkem předání této funkce funkcí vyššího řádu. Např. Funkce G lze implementovat ekvivalentně:

>>> @dvakrát... def G(X):...     vrátit se X + 3>>> G(7)13

Wolfram jazyk

v[1]:=Hnízdo[#+3&,7,2]Ven[1]:=13

Pascal

 1{$ režim objfpc} 2 3typ zábava = funkce(X: Celé číslo): Celé číslo; 4 5funkce přidat3(X: Celé číslo): Celé číslo; 6začít 7  výsledek := X + 3; 8konec; 910funkce dvakrát(func: zábava; X: Celé číslo): Celé číslo;11začít12  výsledek := func(func(X));13konec;1415začít16  writeln(dvakrát(@přidat3, 7)); { 13 }17konec.

F#

nechat dvakrát F = F >> Fnechat F = (+) 3dvakrát F 7 |> printf "%A" // 13

D

int delegát(int) dvakrát(int delegát(int) F){    int dvakrát použito(int X)    {        vrátit se F(F(X));    }    vrátit se &dvakrát použito;}import std.stdio;int plus tři(int X){    vrátit se X + 3;}writeln(dvakrát(&plus tři)(7)); // 13

C#

Func<Func<int, int>, int> dvakrát = F => X => F(F(X));Func<int, int> plus tři = X => X + 3;Řídicí panel.WriteLine(dvakrát(plus tři)(7)); // 13

Haskell

dvakrát :: (A -> A) -> (A -> A)dvakrát F = F . FF :: Num A => A -> AF = odčítat 3hlavní :: IO ()hlavní = tisk (dvakrát F 7) -- 1

Nebo rychleji:

dvakrát F = F . Fhlavní = tisk $ dvakrát (+3) 7 -- 13

Clojure

(defn dvakrát [funkce X]  (funkce (funkce X)))(dvakrát #(+ % 3) 7) ;13

V Clojure začíná „#“ výraz lambda a „%“ odkazuje na další argument funkce.

Systém

(definovat (přidat X y) (+ X y))(definovat (F X)  (lambda (y) (+ X y)))(Zobrazit ((F 3) 7))(Zobrazit (přidat 3 7))

V tomto příkladu schématu funkce vyššího řádu (f x) se používá k implementaci kari. Trvá jediný argument a vrátí funkci. Hodnocení výrazu ((f 3) 7) nejprve vrátí funkci po vyhodnocení (f 3). Vrácená funkce je (lambda (y) (+ 3 y)). Poté vyhodnotí vrácenou funkci se 7 jako argumentem a vrátí 10. Toto je ekvivalent výrazu (přidat 3 7), od té doby (f x) je ekvivalentní kari formě (přidat x y).

Erlang

nebo jinak([], _) -> Nepravdivé;nebo jinak([F | Fs], X) -> nebo jinak(Fs, X, F(X)).nebo jinak(Fs, X, Nepravdivé) -> nebo jinak(Fs, X);nebo jinak(Fs, _, {Nepravdivé, Y}) -> nebo jinak(Fs, Y);nebo jinak(_, _, R) -> R.nebo jinak([zábava erlang:is_integer/1, zábava erlang:is_atom/1, zábava erlang:is_list/1],3.23).

V tomto příkladu Erlang funkce vyššího řádu nebo jinak/ 2 vezme seznam funkcí (Fs) a argument (X). Vyhodnocuje funkci F s argumentem X jako argument. Pokud je funkce F vrací false pak další funkci v Fs budou hodnoceny. Pokud je funkce F se vrací {false, Y} pak další funkce v Fs s argumentem Y budou hodnoceny. Pokud je funkce F se vrací R funkce vyššího řádu nebo jinak/ 2 se vrátí R. Všimněte si, že X, Y, a R mohou být funkce. Příklad se vrátí Nepravdivé.

Elixír

V Elixiru můžete kombinovat definice modulů a anonymní funkce

defmodule Poskok dělat    def dvakrát(F, proti) dělat        F.(F.(proti))    koneckonecpřidat3 = fn(proti) -> 3 + proti konecIO.uvádí Poskok.dvakrát(přidat3, 7) #13

Alternativně můžeme také skládat pomocí čistě anonymních funkcí.

dvakrát = fn(F, proti) -> F.(F.(proti)) konecpřidat3 = fn(proti) -> 3 + proti konecIO.uvádí dvakrát.(přidat3, 7) #13

JavaScript

konst dvakrát = (F, proti) => F(F(proti));konst přidat3 = proti => proti + 3;dvakrát(přidat3, 7); // 13

Jít

func dvakrát(F func(int) int, proti int) int {	vrátit se F(F(proti))}func hlavní() {	F := func(proti int) int {		vrátit se proti + 3	}	dvakrát(F, 7) // vrátí 13}

Všimněte si, že literál funkce lze definovat buď s identifikátorem (dvakrát) nebo anonymně (přiřazeno k proměnné F). Spustit celý program na Jděte na hřiště.

Scala

def dvakrát(F:Int=>Int) = F komponovat Fdvakrát(_+3)(7) // 13

Java (1.8+)

Funkce<IntUnaryOperator, IntUnaryOperator> dvakrát = F -> F.a pak(F);dvakrát.aplikovat(X -> X + 3).applyAsInt(7); // 13

Julie

julia> funkce dvakrát(F)           funkce výsledek(A)               vrátit se F(F(A))               konec           vrátit se výsledek       konecdvakrát (obecná funkce s 1 metodou)julia> plus tři(X) = X + 3plusthree (obecná funkce s 1 metodou)julia> G = dvakrát(plus tři)(:: var "# result # 3" {typeof (plusthree)}) (obecná funkce s 1 metodou)julia> G(7)13

Kotlin

zábava <T> dvakrát(F: (T)->T): (T)->T = {F(F(to))}zábava F(X:Int) = X + 3tisk(dvakrát(::F)(7)) // 13

Lua

místní dvakrát = funkce(F,proti)  vrátit se F(F(proti))konecmístní přidat tři = funkce(proti)  vrátit se proti + 3konectisk(dvakrát(přidat tři,7)) -- 13

MATLAB

funkcevýsledek =dvakrát(fnhandle, v)výsledek = fnhandle(fnhandle(proti));konecpřidat tři = @(n) n + 3;disp(dvakrát(přidat tři, 7)); % 13

Rychlý

// obecná funkcefunc dvakrát<T>(_ proti: @unikající (T) -> T) -> (T) -> T {    vrátit se { proti(proti($0)) }}// odvozené uzavřenínechat F = { $0 + 3 }dvakrát(F)(10) // 16

Rez

// Vezměte funkci f (x), návratovou funkci f (f (x))fn dvakrát<A>(funkce: implFn(A)-> A)-> implFn(A)-> A{hýbat se|A|funkce(funkce(A))}// Zpět x + 3fn plus tři(X: i32)-> i32 {X+3}fn hlavní(){nechatG=dvakrát(plus tři);tisk!("{}",G(7));}

Rubín

def dvakrát(F, X)  F.volání F.volání(X)konecpřidat3 = ->(X) { X + 3 }uvádí dvakrát(přidat3, 7) #=> 13

C

S ukazateli funkcí v C:

#zahrnout <stdio.h>typedef int (*int_func_int) (int);int přidat3(int X) {	vrátit se X + 3;}int dvakrát(int_func_int F, int proti) {	vrátit se F(F(proti));}int hlavní() {	printf("% d n", 		dvakrát(přidat3, 7)	);		vrátit se 0;}

C ++

S obecnými lambdami poskytovanými v C ++ 14:

#zahrnout <iostream>auto dvakrát = [](auto F, int proti){    vrátit se F(F(proti));};    auto F = [](int i){    vrátit se i + 3;}; int hlavní(){       std::cout << dvakrát(F, 7) << std::konec;}

Nebo pomocí std :: funkce v C ++ 11:

#zahrnout <iostream>#zahrnout <functional>auto dvakrát = [](konst std::funkce<int(int)>& F, int proti){    vrátit se F(F(proti));};    auto F = [](int i){    vrátit se i + 3;};    int hlavní(){    std::cout << dvakrát(F, 7) << std::konec;}

D

import std.stdio : writeln;alias dvakrát = (F, i) => F(F(i));alias F = (int i) => i + 3;prázdnota hlavní(){    writeln(dvakrát(F, 7));}

ColdFusion Markup Language (CFML)

dvakrát = funkce(F, proti) {    vrátit se F(F(proti));};F = funkce(proti) {    vrátit se proti + 3;};writeOutput(dvakrát(F, 7)); // 13

PHP

$ dvakrát = fn (Uzavření $ f, int $ v): int => $ f($ f($ v));$ f = fn (int $ v): int => $ v + 3;echo $ dvakrát($ f, 7); // 13

R

dvakrát <- funkce(func) {  vrátit se(funkce(X) {    func(func(X))  })}F <- funkce(X) {  vrátit se(X + 3)}G <- dvakrát(F)> tisk(G(7))[1] 13

Perl

sub přidat3 {    můj ($ x) = @_;    $ x + 3;}sub dvakrát {    můj ($ f) = @_;    sub {        $ f->($ f->(@_));    };}říci dvakrát(\&přidat3)->(7); # 13

nebo se všemi funkcemi v proměnných:

můj $ add3 = sub {    můj ($ x) = @_;    $ x + 3;};můj dvakrát = sub {    můj ($ f) = @_;    sub {        $ f->($ f->(@_));    };};můj $ g = dvakrát->($ add3);říci $ g->(7); # 13

Raku

sub dvakrát(Volatelné: D $ c) {    vrátit se sub { $ c($ c($ ^ x)) };}sub F(Int: D $ x) {    vrátit se $ x + 3;}můj $ g = dvakrát(&F);říci $ g(7); # VÝSTUP: 13

V Raku jsou všechny objekty kódu uzávěry, a proto mohou odkazovat na vnitřní „lexikální“ proměnné z vnějšího rozsahu, protože lexikální proměnná je „uzavřena“ uvnitř funkce. Perl 6 také podporuje syntaxi „pointy block“ pro výrazy lambda, které lze přiřadit k proměnné nebo vyvolat anonymně.

Tcl

soubor dvakrát {{F proti} {aplikovat $ f [aplikovat $ f $ v]}}soubor F {{proti} {vrátit se [expr $ v + 3]}}# výsledek: 13uvádí [aplikovat dvakrát $ f 7]

Tcl používá příkaz apply k použití anonymní funkce (od 8.6).

XQuery

prohlásit funkce místní: dvakrát($F, $X) {  $F($F($X))};prohlásit funkce místní: f($X) {  $X + 3};místní: dvakrát(místní: f#1, 7) (: 13 :)

XACML

Standard XACML definuje funkce vyššího řádu v normě pro použití funkce na více hodnot tašek atributů.

pravidlo allowEntry{    povolení    stav anyOfAny (funkce[stringEqual], občanství, povolené občanství)}

Seznam funkcí vyššího řádu v XACML najdete tady.

Alternativy

Ukazatele funkcí

Ukazatele funkcí v jazycích jako C a C ++ umožnit programátorům předávat odkazy na funkce. Následující C kód vypočítá aproximaci integrálu libovolné funkce:

#zahrnout <stdio.h>dvojnásobek náměstí(dvojnásobek X){    vrátit se X * X;}dvojnásobek krychle(dvojnásobek X){    vrátit se X * X * X;}/ * Vypočítejte integrál f () v intervalu [a, b] * /dvojnásobek integrální(dvojnásobek F(dvojnásobek X), dvojnásobek A, dvojnásobek b, int n){    int i;    dvojnásobek součet = 0;    dvojnásobek dt = (b - A) / n;    pro (i = 0;  i < n;  ++i) {        součet += F(A + (i + 0.5) * dt);    }    vrátit se součet * dt;}int hlavní(){    printf("%G n", integrální(náměstí, 0, 1, 100));    printf("%G n", integrální(krychle, 0, 1, 100));    vrátit se 0;}

The qsort funkce ze standardní knihovny C používá ukazatel funkce k emulaci chování funkce vyššího řádu.

Makra

Makra lze také použít k dosažení některých účinků funkcí vyššího řádu. Makra se však nemohou snadno vyhnout problému zachycení proměnných; mohou také vést k velkému množství duplikovaného kódu, což může být pro kompilátor obtížnější optimalizovat. Makra obvykle nejsou silně typovaná, i když mohou vytvářet silně typovaný kód.

Dynamické vyhodnocení kódu

V jiných imperativní programování jazyků, je možné dosáhnout některých stejných algoritmických výsledků, jaké lze získat pomocí funkcí vyššího řádu dynamickým prováděním kódu (někdy nazývaného Eval nebo Vykonat operace) v rámci hodnocení. Tento přístup může mít značné nevýhody:

• Kód argumentu, který se má provést, obvykle není staticky napsané; tyto jazyky se obecně spoléhají dynamické psaní k určení správnosti a bezpečnosti prováděného kódu.
• Argument se obvykle poskytuje jako řetězec, jehož hodnota nemusí být známa až za běhu. Tento řetězec musí být buď zkompilován během provádění programu (pomocí just-in-time kompilace ) nebo hodnotí výklad, způsobující přidanou režii za běhu a obvykle generující méně efektivní kód.

Objekty

v objektově orientované programování jazyky, které nepodporují funkce vyššího řádu, předměty může být účinnou náhradou. Objekt metody působí v podstatě jako funkce a metoda může přijímat objekty jako parametry a vytvářet objekty jako návratové hodnoty. Objekty však často nesou přidanou režii za běhu ve srovnání s čistými funkcemi a jsou přidány standardní kód pro definování a vytvoření instance objektu a jeho metody (metod). Jazyky, které to umožňují zásobník -založeno (proti halda -založené) objekty nebo struktury může poskytnout větší flexibilitu s touto metodou.

Příklad použití jednoduchého záznamu založeného na zásobníku v Free Pascal s funkcí, která vrací funkci:

program příklad;typ   int = celé číslo;  Txy = záznam X, y: int; konec;  Tf = funkce (xy: Txy): int;     funkce F(xy: Txy): int; začít   Výsledek := xy.y + xy.X; konec;funkce G(func: Tf): Tf; začít   výsledek := func; konec;var   A: Tf;  xy: Txy = (X: 3; y: 7);začít    A := G(@F);     // vrátit funkci do „a“  writeln(A(xy)); // vytiskne 10konec.

Funkce A() bere a Txy záznam jako vstup a vrátí celočíselnou hodnotu součtu záznamu X a y pole (3 + 7).

Defunkcionalizace

Defunkcionalizace lze použít k implementaci funkcí vyššího řádu v jazycích, které chybí prvotřídní funkce:

// Defunkcionalizované funkční datové strukturyšablona<typename T> struktur Přidat { T hodnota; };šablona<typename T> struktur DivBy { T hodnota; };šablona<typename F, typename G> struktur Složení { F F; G G; };// Implementace aplikace s nefunkční funkcíšablona<typename F, typename G, typename X>auto aplikovat(Složení<F, G> F, X arg) {    vrátit se aplikovat(F.F, aplikovat(F.G, arg));}šablona<typename T, typename X>auto aplikovat(Přidat<T> F, X arg) {    vrátit se arg  + F.hodnota;}šablona<typename T, typename X>auto aplikovat(DivBy<T> F, X arg) {    vrátit se arg / F.hodnota;}// Funkce skládání vyšších řádůšablona<typename F, typename G>Složení<F, G> komponovat(F F, G G) {    vrátit se Složení<F, G> {F, G};}int hlavní(int argc, konst char* argv[]) {    auto F = komponovat(DivBy<plovák>{ 2,0f }, Přidat<int>{ 5 });    aplikovat(F, 3); // 4.0f    aplikovat(F, 9); // 7,0 f    vrátit se 0;}

V tomto případě se používají různé typy ke spuštění různých funkcí pomocí přetížení funkce. Přetížená funkce v tomto příkladu má podpis automaticky použít.

Viz také

• Prvotřídní funkce
• Kombinovaná logika
• Programování na funkční úrovni
• Funkcionální programování
• Kappa kalkul - formalismus pro funkce, které vylučuje funkce vyššího řádu
• Strategický vzor
• Zprávy vyššího řádu

Reference