Funcție de ordin superior - Higher-order function

Nu trebuie confundat cu Functor (teoria categoriilor) .

În matematică și informatică , o funcție de ordin superior este o funcție care face cel puțin una dintre următoarele:

  • ia una sau mai multe funcții ca argumente (adică parametrii procedurali ),
  • returnează o funcție ca rezultat.

Toate celelalte funcții sunt funcții de prim ordin . În matematică funcțiile de ordin superior sunt, de asemenea, denumite operatori sau funcționale . Operatorul diferențialului în calcul este un exemplu comun, deoarece mapează o funcție a acestuia derivat , de asemenea , o funcție. Funcțiile de ordin superior nu trebuie confundate cu alte utilizări ale cuvântului „functor” de-a lungul matematicii, vezi Functor (dezambiguizare) .

În calculul lambda netipat , toate funcțiile sunt de ordin superior; într-un calcul lambda tastat , din care sunt derivate majoritatea limbajelor de programare funcționale , funcțiile de ordin superior care iau o funcție ca argument sunt valori cu tipuri de formă .

Exemple generale

  • mapfuncția, găsită în multe limbaje funcționale de programare, este un exemplu de funcție de ordin superior. Ia ca argumente o funcție f și o colecție de elemente și, ca rezultat, returnează o nouă colecție cu f aplicată fiecărui element din colecție.
  • Funcții de sortare, care iau o funcție de comparație ca parametru, permițând programatorului să separe algoritmul de sortare de comparațiile articolelor care sunt sortate. C standard , funcția qsort este un exemplu în acest sens.
  • filtru
  • plia
  • aplica
  • Compoziția funcției
  • Integrare
  • Suna inapoi
  • Traversarea copacilor
  • Gramatica Montague , o teorie semantică a limbajului natural, folosește funcții de ordin superior

Suport în limbaje de programare

Suport direct

Exemplele nu sunt destinate comparării și contrastării limbajelor de programare, ci pentru a servi ca exemple de sintaxă a funcțiilor de ordin superior

În exemplele următoare, funcția de ordin superior twiceia o funcție și aplică funcția la o anumită valoare de două ori. Dacă twicetrebuie aplicat de mai multe ori pentru același flucru, de preferință ar trebui să returneze o funcție mai degrabă decât o valoare. Acest lucru este în conformitate cu principiul „ nu te repeta ”.

APL

Informații suplimentare: APL (limbaj de programare) 
      twice←{⍺⍺ ⍺⍺ ⍵}

      plusthree←{⍵+3}

      g←{plusthree twice ⍵}
    
      g 7
13

Sau într-un mod tacit: 

      twice←⍣2

      plusthree←+∘3

      g←plusthree twice
    
      g 7
13

C ++

Informații suplimentare: C ++

Utilizarea std::functionîn 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
}

Sau, cu lambdas generice furnizate de 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 #

Informații suplimentare: C Sharp (limbaj de programare)

Folosind doar delegați: 

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

Sau echivalent, cu metode statice: 

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

Informații suplimentare: Clojure 
(defn twice [f]
  (fn [x] (f (f x))))

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

(def g (twice plus-three))

(println (g 7)) ; 13

Limbaj de marcare ColdFusion (CFML)

Informații suplimentare: Limbaj de marcare ColdFusion 
twice = function(f) {
    return function(x) {
        return f(f(x));
    };
};

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

g = twice(plusThree);

writeOutput(g(7)); // 13

Lisp comun

Informații suplimentare: Common 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

Informații suplimentare: D (limbaj de programare) 
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
}

Lance

Informații suplimentare: Dart (limbaj de programare) 
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
}

Elixir

Informații suplimentare: Elixir (limbaj de programare)

În Elixir, puteți amesteca definiții ale modulelor și funcții anonime 

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

Alternativ, putem compune și folosind funcții anonime pure. 

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

Informații suplimentare: Erlang (limbaj de programare) 
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).

În acest exemplu Erlang, funcția de ordin superior or_else/2ia o listă de funcții ( Fs) și argument ( X). Evaluează funcția Fcu argumentul Xca argument. Dacă funcția Freturnează fals atunci Fsva fi evaluată următoarea funcție din . Dacă funcția Frevine, va fi evaluată {false, Y}următoarea funcție din Fsargument Y. Dacă funcția Frevine, funcția Rde ordin superior or_else/2va reveni R. Rețineți că X,, Yși Rpot fi funcții. Exemplul revine false.

F #

Informații suplimentare: F Sharp (limbaj de programare) 
let twice f = f >> f

let plus_three = (+) 3

let g = twice plus_three

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

Merge

Informații suplimentare: Go (limbaj de programare) 
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
}

Observați că o funcție literală poate fi definită fie cu un identificator ( twice), fie anonim (atribuit variabilei plusThree).

Haskell

Informații suplimentare: Haskell (limbaj de programare) 
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

Informații suplimentare: J (limbaj de programare)

Explicit, 

   twice=.     adverb : 'u u y'

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

sau tacit, 

   twice=. ^:2

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

Java (1.8+)

Informații suplimentare: Java (limbaj de programare) și istoricul versiunilor Java

Folosind doar interfețe funcționale: 

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

Sau echivalent, cu metode statice: 

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

Informații suplimentare: 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

Informații suplimentare: Julia (limbaj de programare) 
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

Informații suplimentare: Kotlin (limbaj de programare) 
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

Informații suplimentare: Lua (limbaj de programare) 
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

Informații suplimentare: 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

Informații suplimentare: OCaml (limbaj de programare) 
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

Informații suplimentare: 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

sau cu toate funcțiile în variabile: 

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

Rețineți că funcțiile săgeată captează implicit orice variabilă care provine din domeniul de aplicare părinte, în timp ce funcțiile anonime necesită usecuvântul cheie să facă același lucru.

Perl

Informații suplimentare: 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

sau cu toate funcțiile în variabile: 

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

Piton

Informații suplimentare: Python (limbaj de programare) 
>>> def twice(f):
...     def result(x):
...         return f(f(x))
...     return result

>>> plusthree = lambda i: i + 3

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

Sintaxa decoratorului Python este adesea utilizată pentru a înlocui o funcție cu rezultatul trecerii acelei funcții printr-o funcție de ordin superior. De exemplu, funcția gar putea fi implementată în mod echivalent: 

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

>>> g(7)
13

R

Informații suplimentare: R (limbaj de programare) 
twice <- function(f) {
  return(function(x) {
    f(f(x))
  })
}

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

g <- twice(plusThree)

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

Raku

Informații suplimentare: Raku (limbaj de programare) 
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

În Raku, toate obiectele de cod sunt închideri și, prin urmare, pot face referință la variabilele "lexicale" interioare dintr-un domeniu de aplicare extern, deoarece variabila lexicală este "închisă" în interiorul funcției. Raku acceptă, de asemenea, sintaxa „bloc punctat” pentru expresiile lambda care pot fi atribuite unei variabile sau invocate anonim.

Rubin

Informații suplimentare: Ruby (limbaj de programare) 
def twice(f)
  ->(x) { f.call f.call(x) }
end

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

g = twice(plus_three)

puts g.call(7) # 13

Rugini

Informații suplimentare: Rust (limbaj de programare) 
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

Informații suplimentare: Scala (limbaj de programare) 
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
  }
}

Sistem

Informații suplimentare: Schemă (limbaj de programare) 
(define (add x y) (+ x y))
(define (f x)
  (lambda (y) (+ x y)))
(display ((f 3) 7))
(display (add 3 7))

În acest exemplu de schemă, funcția de ordin superior (f x)este utilizată pentru a implementa currying . Este nevoie de un singur argument și returnează o funcție. Evaluarea expresiei ((f 3) 7)returnează mai întâi o funcție după evaluare (f 3). Funcția returnată este (lambda (y) (+ 3 y)). Apoi, evaluează funcția returnată cu 7 ca argument, returnând 10. Aceasta este echivalentă cu expresia (add 3 7), deoarece (f x)este echivalentă cu forma curri a lui (add x y).

Rapid

Informații suplimentare: Swift (limbaj de programare) 
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

Informații suplimentare: 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 folosește comanda apply pentru a aplica o funcție anonimă (de la 8.6).

XACML

Informații suplimentare: XACML

Standardul XACML definește funcții de ordin superior în standard pentru a aplica o funcție valorilor multiple ale pungilor de atribute. 

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

Lista funcțiilor de ordin superior din XACML poate fi găsită aici .

XQuery

Informații suplimentare: XQuery 
declare function local:twice($f, $x) {
  $f($f($x))
};

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

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

Alternative

Indicații funcționale

Indicatorii de funcții în limbaje precum C , C ++ și Pascal permit programatorilor să transmită referințe la funcții. Următorul cod C calculează o aproximare a integralei unei funcții arbitrare: 

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

Funcția qsort din biblioteca standard C utilizează un indicator de funcție pentru a emula comportamentul unei funcții de ordin superior.

Macrocomenzi

Macro-urile pot fi, de asemenea, utilizate pentru a obține unele dintre efectele funcțiilor de ordin superior. Cu toate acestea, macrocomenzile nu pot evita cu ușurință problema capturării variabilei; acestea pot duce, de asemenea, la cantități mari de cod duplicat, ceea ce poate fi mai dificil de optimizat pentru un compilator. În general, macro-urile nu sunt puternic tastate, deși pot produce cod puternic tastat.

Evaluare dinamică a codului

În alte limbaje de programare imperative , este posibil să se obțină aceleași rezultate algoritmice ca și cele obținute prin funcții de ordin superior prin executarea dinamică a codului (uneori numit operații Eval sau Execute ) în domeniul evaluării. Această abordare poate avea dezavantaje semnificative:

  • Codul argumentului care trebuie executat nu este de obicei scris tipic ; aceste limbi se bazează, în general, pe tastarea dinamică pentru a determina formarea și siguranța codului care trebuie executat.
  • Argumentul este de obicei furnizat ca un șir, a cărui valoare poate să nu fie cunoscută decât în ​​timpul rulării. Acest șir trebuie fie compilat în timpul execuției programului (utilizând o compilare just-in-time ), fie evaluat prin interpretare , provocând unele cheltuieli suplimentare în timpul rulării și, de obicei, generând cod mai puțin eficient.

Obiecte

În limbajele de programare orientate obiect care nu acceptă funcții de ordin superior, obiectele pot fi un substitut eficient. Metodele unui obiect acționează în esență, precum funcțiile, iar o metodă poate accepta obiecte ca parametri și produce obiecte ca valori returnate. Obiectele poartă deseori un timp de execuție adăugat în comparație cu funcțiile pure, totuși și au adăugat un cod boilerplate pentru definirea și instanțierea unui obiect și a metodei acestuia. Limbile care permit obiecte sau structuri bazate pe stivă (versus stivă ) pot oferi mai multă flexibilitate cu această metodă.

Un exemplu de utilizare a unei înregistrări simple bazate pe stivă în Free Pascal cu o funcție care returnează o funcție: 

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.

Funcția a()ia o Txyînregistrare ca intrare și returnează valoarea întreagă a sumei înregistrării xși a ycâmpurilor (3 + 7).

Defuncționalizare

Defuncționalizarea poate fi utilizată pentru a implementa funcții de ordin superior în limbi care nu au funcții de primă clasă : 

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

În acest caz, diferite tipuri sunt utilizate pentru a declanșa funcții diferite prin supraîncărcarea funcției . Funcția supraîncărcată din acest exemplu are semnătura auto apply.

Vezi si

Referințe