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

V matematice a informatice , je funkce vyššího řádu je funkce , která dělá alespoň jednu z následujících možností:

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

Všechny ostatní funkce jsou funkce prvního řádu . V matematice jsou funkce vyššího řádu také označovány jako operátory nebo funkcionály . Diferenciální operátor v počtu je obyčejný příklad, protože mapuje funkce jeho derivát , také funkci. Funkce vyššího řádu by neměly být zaměňovány s jinými způsoby použití slova „funktor“ v celé matematice, viz Funktor (disambiguation) .

V netypickém lambda kalkulu jsou všechny funkce vyššího řádu; v typovaném lambda kalkulu , ze kterého je odvozena většina funkčních programovacích jazyků, jsou funkce vyššího řádu, které berou jako argument jednu funkci, hodnoty s typy formuláře . ${\ Displaystyle (\ tau _ {1} \ to \ tau _ {2}) \ to \ tau _ {3}}$

Obecné příklady

mapfunkce, nalezená v mnoha funkčních programovacích jazycích, je jedním z příkladů funkce vyššího řádu. To bere jako argumenty funkci f a kolekci prvků a v důsledku toho vrací novou kolekci s f aplikovanou na každý prvek z kolekce.
Třídící funkce, které berou srovnávací funkci jako parametr, což umožňuje programátorovi oddělit třídicí algoritmus od porovnání tříděných položek. C standardní funkce qsort je příkladem.
filtr
složit
aplikovat
Složení funkce
Integrace
Zpětné volání
Procházení stromů
Montague gramatika , sémantická teorie přirozeného jazyka, používá funkce vyššího řádu

Podpora v programovacích jazycích

Přímá podpora

Příklady nejsou určeny k porovnává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 twicepřebírá funkci a aplikuje funkci na nějakou hodnotu dvakrát. Pokud twicemá být pro totéž aplikováno několikrát, fmělo by přednostně vrátit funkci spíše než hodnotu. To je v souladu se zásadou „ neopakujte se “.

APL

      twice←{⍺⍺ ⍺⍺ ⍵}

      plusthree←{⍵+3}

      g←{plusthree twice ⍵}
    
      g 7
13

Nebo mlčky:

      twice←⍣2

      plusthree←+∘3

      g←plusthree twice
    
      g 7
13

C ++

Použití std::functionv C ++ 11:

#include <iostream>
#include <functional>

auto twice = [](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 = twice(plus_three);

    std::cout << g(7) << '\n'; // 13
}

Nebo s generickými lambdy poskytovanými C ++ 14:

#include <iostream>

auto twice = [](const auto& f)
{
    return [&f](int x) {
        return f(f(x));
    };
};

auto plus_three = [](int i)
{
    return i + 3;
};

int main()
{
    auto g = twice(plus_three);

    std::cout << g(7) << '\n'; // 13
}

C#

Použití pouze delegátů:

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
    }
}

Nebo ekvivalentně se statickými metodami:

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
    }
}

Clojure

(defn twice [f]
  (fn [x] (f (f x))))

(defn plus-three [i]
  (+ i 3))

(def g (twice plus-three))

(println (g 7)) ; 13

ColdFusion Markup Language (CFML)

twice = function(f) {
    return function(x) {
        return f(f(x));
    };
};

plusThree = function(i) {
    return i + 3;
};

g = twice(plusThree);

writeOutput(g(7)); // 13

Lisp

(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))

D

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
}

Šipka

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
}

Elixír

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

defmodule Hof do
    def twice(f) do
        fn(x) -> f.(f.(x)) end
    end
end

plus_three = fn(i) -> 3 + i end

g = Hof.twice(plus_three)

IO.puts g.(7) # 13

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

twice = fn(f) ->
    fn(x) -> f.(f.(x)) end
end

plus_three = fn(i) -> 3 + i end

g = twice.(plus_three)

IO.puts g.(7) # 13

Erlang

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).

V tomto příkladu Erlang funkce vyššího řádu or_else/2přebírá seznam funkcí ( Fs) a argument ( X). Vyhodnocuje funkci Fs argumentem Xjako argumentem. Pokud funkce Fvrátí hodnotu false, Fsbude vyhodnocena další funkce v . Pokud se funkce Fvrátí, bude vyhodnocena {false, Y}další funkce Fss argumentem Y. Pokud funkce Fvrátí Rfunkce vyššího řádu or_else/2vrátí R. Všimněte si, že X, Ya Rmohou být funkce. Příklad se vrátí false.

F#

let twice f = f >> f

let plus_three = (+) 3

let g = twice plus_three

g 7 |> printf "%A" // 13

Jít

package main

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 := twice(plusThree)

	fmt.Println(g(7)) // 13
}

Všimněte si, že literál funkce může být definován buď pomocí identifikátoru ( twice) nebo anonymně (přiřazen proměnné plusThree).

Haskell

twice :: (Int -> Int) -> (Int -> Int)
twice f = f . f

plusThree :: Int -> Int
plusThree = (+3)

main :: IO ()
main = print (g 7) -- 13
  where
    g = twice plusThree

J.

Výslovně,

   twice=.     adverb : 'u u y'

   plusthree=. verb   : 'y + 3'
   
   g=. plusthree twice
   
   g 7
13

nebo mlčky,

   twice=. ^:2

   plusthree=. +&3
   
   g=. plusthree twice
   
   g 7
13

Java (1,8+)

Pomocí pouze funkčních rozhraní:

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
    }
}

Nebo ekvivalentně se statickými metodami:

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
    }
}

JavaScript

"use strict";

const twice = f => x => f(f(x));

const plusThree = i => i + 3;

const g = twice(plusThree);

console.log(g(7)); // 13

Julie

julia> function twice(f)
           function result(x)
               return f(f(x))
           end
           return result
       end
twice (generic function with 1 method)

julia> plusthree(i) = i + 3
plusthree (generic function with 1 method)

julia> g = twice(plusthree)
(::var"#result#3"{typeof(plusthree)}) (generic function with 1 method)

julia> g(7)
13

Kotlin

fun twice(f: (Int) -> Int): (Int) -> Int {
    return { f(f(it)) }
}

fun plusThree(i: Int) = i + 3

fun main() {
    val g = twice(::plusThree)

    println(g(7)) // 13
}

Lua

function twice(f)
  return function (x)
    return f(f(x))
  end
end

function plusThree(i)
  return i + 3
end

local g = twice(plusThree)

print(g(7)) -- 13

MATLAB

function result = twice(f)
    result = @inner

    function val = inner(x)
        val = f(f(x));
    end
end

plusthree = @(i) i + 3;

g = twice(plusthree)

disp(g(7)); % 13

OCaml

let twice f x =
  f (f x)

let plus_three =
  (+) 3

let () =
  let g = twice plus_three in

  print_int (g 7); (* 13 *)
  print_newline ()

PHP

<?php

declare(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

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

<?php

declare(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

Všimněte si toho, že funkce šipek implicitně zachycují všechny proměnné, které pocházejí z nadřazeného oboru, zatímco anonymní funkce vyžadují, aby useklíčové slovo udělalo totéž.

Perl

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

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

use strict;
use warnings;

my $twice = sub {
    my ($f) = @_;
    sub {
        $f->($f->(@_));
    };
};

my $plusThree = sub {
    my ($x) = @_;
    $x + 3;
};

my $g = $twice->($plusThree);

print $g->(7), "\n"; # 13

Krajta

>>> def twice(f):
...     def result(x):
...         return f(f(x))
...     return result

>>> plusthree = lambda i: i + 3

>>> g = twice(plusthree)
    
>>> 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. Tuto funkci glze například implementovat ekvivalentně:

>>> @twice
... def g(i):
...     return i + 3

>>> g(7)
13

R.

twice <- function(f) {
  return(function(x) {
    f(f(x))
  })
}

plusThree <- function(i) {
  return(i + 3)
}

g <- twice(plusThree)

> print(g(7))
[1] 13

Raku

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

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 uvnitř funkce „uzavřená“. Raku také podporuje syntaxi „pointy block“ pro výrazy lambda, které lze přiřadit proměnné nebo je vyvolat anonymně.

Rubín

def twice(f)
  ->(x) { f.call f.call(x) }
end

plus_three = ->(i) { i + 3 }

g = twice(plus_three)

puts g.call(7) # 13

Rez

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
}

Scala

object Main {
  def twice(f: Int => Int): Int => Int =
    f compose f

  def plusThree(i: Int): Int =
    i + 3

  def main(args: Array[String]): Unit = {
    val g = twice(plusThree)

    print(g(7)) // 13
  }
}

Systém

(define (add x y) (+ x y))
(define (f x)
  (lambda (y) (+ x y)))
(display ((f 3) 7))
(display (add 3 7))

V tomto příkladu schématu (f x)se k implementaci curryingu používá funkce vyššího řádu . Trvá jeden argument a vrátí funkci. Vyhodnocení 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 s argumentem 7 a vrátí hodnotu 10. Toto je ekvivalentní výrazu (add 3 7), protože (f x)je ekvivalentní curry formě (add x y).

Rychlý

func twice(_ f: @escaping (Int) -> Int) -> (Int) -> Int {
    return { f(f($0)) }
}

let plusThree = { $0 + 3 }

let g = twice(plusThree)

print(g(7)) // 13

Tcl

set twice {{f x} {apply $f [apply $f $x]}}
set plusThree {{i} {return [expr $i + 3]}}

# result: 13
puts [apply $twice $plusThree 7]

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

XACML

Standard XACML definuje ve standardu funkce vyššího řádu pro použití funkce na více hodnot sáčků atributů.

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

Seznam funkcí vyššího řádu v XACML naleznete zde .

XQuery

declare function local:twice($f, $x) {
  $f($f($x))
};

declare function local:plusthree($i) {
  $i + 3
};

local:twice(local:plusthree#1, 7) (: 13 :)

Alternativy

Ukazatele funkcí

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

#include <stdio.h>

double square(double x)
{
    return x * x;
}

double cube(double x)
{
    return x * x * x;
}

/* Compute the integral of f() within the interval [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;
}

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

Makra

K dosažení některých efektů funkcí vyššího řádu lze také použít makra . 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 obecně nejsou silně zadaná, i když mohou vytvářet silně zadaný kód.

Dynamické vyhodnocení kódu

V jiných imperativních programovacích jazycích je možné dosáhnout některých stejných algoritmických výsledků, jaké jsou získány prostřednictvím funkcí vyššího řádu, dynamickým prováděním kódu (někdy nazývaného operace Eval nebo Execute ) v rozsahu vyhodnocení. Tento přístup může mít značné nevýhody:

Kód argumentu, který má být spuštěn, obvykle není staticky zadán ; tyto jazyky obecně spoléhají na dynamické psaní, aby určily dobře vytvořenou a bezpečnou verzi kódu, který má být spuštěn.
Argument je obvykle poskytován 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í kompilace just-in-time ), nebo vyhodnocen interpretací , což způsobí přidanou režii za běhu a obvykle generuje méně účinný kód.

Objekty

V objektově orientovaných programovacích jazycích, které nepodporují funkce vyššího řádu, mohou být objekty efektivní náhradou. Metody objektu fungují 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 ve srovnání s čistými funkcemi často nesou přidanou režii za běhu a přidávají standardní kód pro definování a vytváření instancí objektu a jeho metod. Jazyky, které umožňují objekty nebo struktury založené na hromádce (versus hromady ), mohou s touto metodou poskytnout větší flexibilitu.

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

program example;

type 
  int = integer;
  Txy = record x, y: int; end;
  Tf = function (xy: Txy): int;
     
function f(xy: Txy): int; 
begin 
  Result := xy.y + xy.x; 
end;

function g(func: Tf): Tf; 
begin 
  result := func; 
end;

var 
  a: Tf;
  xy: Txy = (x: 3; y: 7);

begin  
  a := g(@f);     // return a function to "a"
  writeln(a(xy)); // prints 10
end.

Funkce a()vezme Txyzáznam jako vstup a vrátí celočíselnou hodnotu součtu záznamů xa ypolí (3 + 7).

Defunkcionalizace

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

// Defunctionalized function data structures
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; };

// Defunctionalized function application implementations
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;
}

// Higher-order compose function
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;
}

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

Viz také

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

Languages

In other projects