Funkcja wyższego rzędu - Higher-order function

W matematyce i informatyce , A funkcja wyższego rzędu jest funkcja , która ma co najmniej jedną z następujących czynności:

przyjmuje jedną lub więcej funkcji jako argumenty (np. parametry proceduralne ),
zwraca funkcję jako wynik.

Wszystkie inne funkcje są funkcjami pierwszego rzędu . W matematyce funkcje wyższego rzędu są również nazywane operatorami lub funkcjonałami . Różnica operatora w rachunku jest typowym przykładem, ponieważ odwzorowuje funkcji jego pochodnej , również funkcję. Funkcje wyższego rzędu nie powinny być mylone z innymi zastosowaniami słowa „funktor” w matematyce, patrz Functor (ujednoznacznienie) .

W nieopisanym rachunku lambda wszystkie funkcje są wyższego rzędu; w typowanym rachunku lambda , z którego wywodzi się większość funkcjonalnych języków programowania, funkcje wyższego rzędu, które przyjmują jedną funkcję jako argument, są wartościami z typami form . ${\ Displaystyle (\ tau _ {1} \ do \ tau _ {2}) \ do \ tau _ {3}}$

Ogólne przykłady

mapFunkcja, występująca w wielu funkcjonalnych językach programowania, jest jednym z przykładów funkcji wyższego rzędu. Jako argumenty przyjmuje funkcję f i kolekcję elementów, w wyniku czego zwraca nową kolekcję z f zastosowanym do każdego elementu z kolekcji.
Funkcje sortujące, które przyjmują funkcję porównania jako parametr, umożliwiając programiście oddzielenie algorytmu sortowania od porównań sortowanych elementów. C standardowa funkcja qsort jest przykładem.
filtr
zginać
zastosować
Skład funkcji
Integracja
Oddzwonić
Przemierzanie drzewa
Gramatyka Montague , semantyczna teoria języka naturalnego, wykorzystuje funkcje wyższego rzędu

Wsparcie w językach programowania

Bezpośrednie wsparcie

Przykłady nie mają na celu porównywania i kontrastowania języków programowania, ale służą jako przykłady składni funkcji wyższego rzędu

W poniższych przykładach funkcja wyższego rzędu twiceprzyjmuje funkcję i stosuje ją dwukrotnie do pewnej wartości. Jeśli twicema być zastosowany kilka razy dla tego samego f, najlepiej, aby zwracał funkcję, a nie wartość. Jest to zgodne z zasadą „ nie powtarzaj się ”.

APL

      twice←{⍺⍺ ⍺⍺ ⍵}

      plusthree←{⍵+3}

      g←{plusthree twice ⍵}
    
      g 7
13

Lub w sposób milczący:

      twice←⍣2

      plusthree←+∘3

      g←plusthree twice
    
      g 7
13

C++

Korzystanie std::functionw 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
}

Lub z generycznymi lambdami dostarczonymi przez 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#

Korzystanie tylko z delegatów:

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

Lub równoważnie za pomocą metod statycznych:

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

Język znaczników ColdFusion (CFML)

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

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

g = twice(plusThree);

writeOutput(g(7)); // 13

Wspólne seplenienie

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

Strzałka

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
}

Eliksir

W Elixirze możesz mieszać definicje modułów i funkcje anonimowe

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

Alternatywnie możemy również komponować używając czystych funkcji anonimowych.

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

W tym przykładzie Erlanga funkcja wyższego rzędu or_else/2pobiera listę funkcji ( Fs) i argument ( X). Ocenia funkcję Fz argumentem Xjako argumentem. Jeśli funkcja Fzwróci fałsz, Fszostanie oceniona następna funkcja w . Jeśli funkcja Fzwróci, {false, Y}to następna funkcja Fsz argumentem Yzostanie oceniona. Jeśli funkcja Fzwraca, funkcja Rwyższego rzędu or_else/2zwróci R. Zauważ, że X, Yi Rmogą być funkcjami. Przykład zwraca false.

F#

let twice f = f >> f

let plus_three = (+) 3

let g = twice plus_three

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

Udać się

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
}

Zauważ, że literał funkcji może być zdefiniowany z identyfikatorem ( twice) lub anonimowo (przypisany do zmiennej 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

Wyraźnie,

   twice=.     adverb : 'u u y'

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

lub milcząco,

   twice=. ^:2

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

Jawa (1.8+)

Używając tylko funkcjonalnych interfejsów:

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

Lub równoważnie za pomocą metod statycznych:

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

Julia

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

lub ze wszystkimi funkcjami w zmiennych:

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

Należy zauważyć, że funkcje strzałek niejawnie przechwytują wszystkie zmienne pochodzące z zakresu nadrzędnego, podczas gdy funkcje anonimowe wymagają tego samego usesłowa kluczowego.

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

lub ze wszystkimi funkcjami w zmiennych:

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

Pyton

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

>>> plusthree = lambda i: i + 3

>>> g = twice(plusthree)
    
>>> g(7)
13

Składnia dekoratora Pythona jest często używana do zastępowania funkcji wynikiem przekazania tej funkcji przez funkcję wyższego rzędu. Np. funkcja gmoże być zaimplementowana równoważnie:

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

W Raku wszystkie obiekty kodu są domknięciami i dlatego mogą odwoływać się do wewnętrznych zmiennych „leksykalnych” z zewnętrznego zakresu, ponieważ zmienna leksykalna jest „zamknięta” wewnątrz funkcji. Raku obsługuje również składnię "pointy block" dla wyrażeń lambda, które można przypisać do zmiennej lub wywoływać anonimowo.

Rubin

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

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

g = twice(plus_three)

puts g.call(7) # 13

Rdza

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

Schemat

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

W tym przykładzie schematu funkcja wyższego rzędu (f x)jest używana do implementacji currying . Pobiera pojedynczy argument i zwraca funkcję. Ocena wyrażenia ((f 3) 7)najpierw zwraca funkcję po ocenie (f 3). Zwróconą funkcją jest (lambda (y) (+ 3 y)). Następnie oblicza zwróconą funkcję z 7 jako argumentem, zwracając 10. Jest to równoważne wyrażeniu (add 3 7), ponieważ (f x)jest równoważne z curried postaci (add x y).

Szybki

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 używa polecenia apply do zastosowania funkcji anonimowej (od wersji 8.6).

XACML

Standard XACML definiuje funkcje wyższego rzędu w standardzie w celu zastosowania funkcji do wielu wartości toreb atrybutów.

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

Listę funkcji wyższego rzędu w XACML można znaleźć tutaj .

XZapytanie

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

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

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

Alternatywy

Wskaźniki funkcji

Wskaźniki do funkcji w językach takich jak C , C++ i Pascal umożliwiają programistom przekazywanie odwołań do funkcji. Poniższy kod C oblicza przybliżenie całki dowolnej funkcji:

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

Funkcja qsort z biblioteki standardowej C używa wskaźnika funkcji do emulowania zachowania funkcji wyższego rzędu.

Makra

Makra można również wykorzystać do osiągnięcia niektórych efektów funkcji wyższego rzędu. Jednak makra nie mogą łatwo uniknąć problemu przechwytywania zmiennych; mogą również powodować duże ilości zduplikowanego kodu, co może być trudniejsze do optymalizacji dla kompilatora. Makra zazwyczaj nie są silnie typizowane, chociaż mogą generować silnie typizowany kod.

Dynamiczna ocena kodu

W innych imperatywnych językach programowania możliwe jest osiągnięcie niektórych z tych samych wyników algorytmicznych, jakie uzyskuje się za pomocą funkcji wyższego rzędu, dynamicznie wykonując kod (czasami nazywany operacjami Eval lub Execute ) w zakresie oceny. Takie podejście może mieć poważne wady:

Kod argumentu do wykonania zwykle nie jest wpisany statycznie ; języki te zazwyczaj opierają się na dynamicznym typowaniu w celu określenia poprawności i bezpieczeństwa kodu, który ma zostać wykonany.
Argument jest zwykle dostarczany jako ciąg, którego wartość może nie być znana do czasu wykonania. Ten ciąg musi być kompilowany podczas wykonywania programu (przy użyciu kompilacji just-in-time ) lub oceniany przez interpretację , powodując dodatkowe obciążenie w czasie wykonywania i zwykle generując mniej wydajny kod.

Obiekty

W obiektowych językach programowania , które nie obsługują funkcji wyższego rzędu, obiekty mogą być skutecznym substytutem. Metody obiektu działają zasadniczo jak funkcje, a metoda może akceptować obiekty jako parametry i generować obiekty jako wartości zwracane. Jednak obiekty często niosą ze sobą dodatkowe obciążenie w czasie wykonywania w porównaniu z czystymi funkcjami, a także dodany standardowy kod do definiowania i tworzenia instancji obiektu i jego metod. Języki, które zezwalają na obiekty lub struktury oparte na stosie (w przeciwieństwie do sterty ), mogą zapewnić większą elastyczność dzięki tej metodzie.

Przykład użycia prostego rekordu opartego na stosie w Free Pascal z funkcją zwracającą funkcję:

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.

Funkcja a()pobiera Txyrekord jako dane wejściowe i zwraca całkowitą wartość sumy rekordów xi ypól (3 + 7).

Defunkcjonalizacja

Defunkcjonalizacja może być wykorzystana do implementacji funkcji wyższego rzędu w językach, w których brakuje funkcji pierwszej klasy :

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

W tym przypadku różne typy są używane do wyzwalania różnych funkcji poprzez przeciążanie funkcji . Przeciążona funkcja w tym przykładzie ma sygnaturę auto apply.

Zobacz też

Pierwszorzędna funkcja
Logika kombinacyjna
Programowanie na poziomie funkcji
Programowanie funkcjonalne
Rachunek Kappa - formalizm dla funkcji, który wyklucza funkcje wyższego rzędu
Wzór strategii
Wiadomości wyższego rzędu

Languages

In other projects