Функция высшего порядка
 | Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( сентябрь 2013 г. ) |
В математике и информатике функция высшего порядка ( HOF ) — это функция , которая выполняет хотя бы одно из следующих действий:
- принимает в качестве аргументов одну или несколько функций (т. е. процедурный параметр , который является параметром процедуры , которая сама является процедурой),
- возвращает функцию в качестве результата.
Все остальные функции являются функциями первого порядка . В математике функции высшего порядка также называются операторами или функционалами . Дифференциальный оператор в исчислении является распространенным примером, поскольку он отображает функцию в ее производную , которая также является функцией. Функции высшего порядка не следует путать с другими значениями слова «функтор» в математике, см. Функтор (значения) .
В нетипизированном лямбда-исчислении все функции имеют более высокий порядок; в типизированном лямбда-исчислении , от которого произошло большинство функциональных языков программирования, функции высшего порядка, принимающие одну функцию в качестве аргумента, представляют собой значения с типами вида .
Общие примеры [ править ]
mapФункция, встречающаяся во многих языках функционального программирования, является одним из примеров функции высшего порядка. В качестве аргументов он принимает функцию f и коллекцию элементов и в результате возвращает новую коллекцию, в которой f применяется к каждому элементу коллекции.- Функции сортировки, которые принимают функцию сравнения в качестве параметра, что позволяет программисту отделить алгоритм сортировки от сравнения сортируемых элементов. функция C Стандартная
qsortявляется примером этого. - фильтр
- складывать
- применять
- Функциональная композиция
- Интеграция
- Перезвонить
- Обход дерева
- Грамматика Монтегю , семантическая теория естественного языка, использует функции высшего порядка.
Поддержка языков программирования [ править ]
Прямая поддержка [ править ]
Эти примеры не предназначены для сравнения и противопоставления языков программирования, а служат примерами синтаксиса функций высшего порядка.
В следующих примерах функция высшего порядка twice принимает функцию и дважды применяет ее к некоторому значению. Если twice необходимо применять несколько раз для одного и того же f желательно, чтобы он возвращал функцию, а не значение. Это соответствует принципу « не повторяйся ».
АПЛ [ править ]
twice←{⍺⍺ ⍺⍺ ⍵}
plusthree←{⍵+3}
g←{plusthree twice ⍵}
g 7
13
Или молчаливо:
twice←⍣2
plusthree←+∘3
g←plusthree twice
g 7
13
С++ [ править ]
С использованием std::function в С++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
}
Или с помощью общих лямбда-выражений, предоставляемых 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
}
С# [ править ]
Использование только делегатов:
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
}
}
Или, что то же самое, со статическими методами:
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 (twice plus-three))
(println (g 7)) ; 13
Язык разметки 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
Общий Лисп [ править ]
(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
}
Эликсир [ править ]
В Elixir вы можете смешивать определения модулей и анонимные функции.
defmodule Hof do
def twice(f) do
fn(x) -> f.(f.(x)) end
end
end
plus_three = fn(i) -> i + 3 end
g = Hof.twice(plus_three)
IO.puts g.(7) # 13
В качестве альтернативы мы также можем использовать чистые анонимные функции.
twice = fn(f) ->
fn(x) -> f.(f.(x)) end
end
plus_three = fn(i) -> i + 3 end
g = twice.(plus_three)
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).
В этом примере Erlang функция высшего порядка or_else/2 принимает список функций ( Fs) и аргумент ( X). Он оценивает функцию F с аргументом X как аргумент. Если функция F возвращает false, затем следующая функция в Fs будет оценено. Если функция F возвращает {false, Y} затем следующая функция в Fs с аргументом Y будет оценено. Если функция F возвращает R функция высшего порядка or_else/2 вернется R. Обратите внимание, что X, Y, и R могут быть функциями. Пример возвращает false.
Ф# [ править ]
let twice f = f >> f
let plus_three = (+) 3
let g = twice plus_three
g 7 |> printf "%A" // 13
Иди [ править ]
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
}
Обратите внимание, что литерал функции может быть определен либо с помощью идентификатора ( twice) или анонимно (присваивается переменной plusThree).
Хаскелл [ править ]
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
Дж [ править ]
Явно,
twice=. adverb : 'u u y'
plusthree=. verb : 'y + 3'
g=. plusthree twice
g 7
13
или молчаливо,
twice=. ^:2
plusthree=. +&3
g=. plusthree twice
g 7
13
Java (1.8+) [ править ]
Использование только функциональных интерфейсов:
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
}
}
Или, что то же самое, со статическими методами:
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
Или с классическим синтаксисом:
"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 (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
Котлин [ править ]
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
}
Луа [ править ]
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
МАТЛАБ [ править ]
function result = twice(f)
result = @(x) f(f(x));
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
или со всеми функциями в переменных:
<?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
Обратите внимание, что стрелочные функции неявно захватывают любые переменные, поступающие из родительской области видимости. [1] тогда как анонимные функции требуют use ключевое слово, чтобы сделать то же самое.
Перл [ править ]
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
или со всеми функциями в переменных:
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):
... def result(x):
... return f(f(x))
... return result
>>> plus_three = lambda i: i + 3
>>> g = twice(plus_three)
>>> g(7)
13
Синтаксис декоратора Python часто используется для замены функции результатом передачи этой функции через функцию более высокого порядка. Например, функция g может быть реализовано эквивалентно:
>>> @twice
... def g(i):
... return i + 3
>>> g(7)
13
Р [ править ]
twice <- function(f) {
return(function(x) {
f(f(x))
})
}
plusThree <- function(i) {
return(i + 3)
}
g <- twice(plusThree)
> print(g(7))
[1] 13
Raku [ edit ]
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
В Raku все объекты кода являются замыканиями и поэтому могут ссылаться на внутренние «лексические» переменные из внешней области, поскольку лексическая переменная «закрыта» внутри функции. Raku также поддерживает синтаксис «заостренного блока» для лямбда-выражений, которые можно назначать переменной или вызывать анонимно.
Руби [ править ]
def twice(f)
->(x) { f.call(f.call(x)) }
end
plus_three = ->(i) { i + 3 }
g = twice(plus_three)
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 f
def plusThree(i: Int): Int =
i + 3
def main(args: Array[String]): Unit = {
val g = twice(plusThree)
print(g(7)) // 13
}
}
Схема [ править ]
(define (twice f)
(lambda (x) (f (f x))))
(define (plus-three i)
(+ i 3))
(define g (twice plus-three))
(display (g 7)) ; 13
(display "\n")
Свифт [ править ]
func twice(_ f: @escaping (Int) -> Int) -> (Int) -> Int {
return { f(f($0)) }
}
let plusThree = { $0 + 3 }
let g = twice(plusThree)
print(g(7)) // 13
ТКЛ [ править ]
set twice {{f x} {apply $f [apply $f $x]}}
set plusThree {{i} {return [expr $i + 3]}}
# result: 13
puts [apply $twice $plusThree 7]
Tcl использует команду Apply для применения анонимной функции (начиная с версии 8.6).
XACML [ править ]
Стандарт XACML определяет в стандарте функции более высокого порядка для применения функции к нескольким значениям пакетов атрибутов.
rule allowEntry{
permit
condition anyOfAny(function[stringEqual], citizenships, allowedCitizenships)
}
Список функций высшего порядка в XACML можно найти здесь .
XQuery [ править ]
declare function local:twice($f, $x) {
$f($f($x))
};
declare function local:plusthree($i) {
$i + 3
};
local:twice(local:plusthree#1, 7) (: 13 :)
Альтернативы [ править ]
Указатели функций [ править ]
Указатели функций в таких языках, как C , C++ , Fortran и Pascal , позволяют программистам передавать ссылки на функции. Следующий код C вычисляет приближение интеграла произвольной функции:
#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;
}
Функция qsort из стандартной библиотеки C использует указатель на функцию для эмуляции поведения функции более высокого порядка.
Макросы [ править ]
Макросы также можно использовать для достижения некоторых эффектов функций более высокого порядка. Однако макросы не могут легко избежать проблемы захвата переменных; они также могут привести к большому количеству дублированного кода, который компилятору может быть сложнее оптимизировать. Макросы, как правило, не являются строго типизированными, хотя они могут создавать строго типизированный код.
Динамическая оценка кода [ править ]
В других императивных языках программирования можно достичь некоторых из тех же алгоритмических результатов, которые получаются с помощью функций более высокого порядка, путем динамического выполнения кода (иногда называемого операциями Eval или Execute ) в области оценки. У такого подхода могут быть существенные недостатки:
- Код аргумента, который должен быть выполнен, обычно не является статически типизированным ; эти языки обычно полагаются на динамическую типизацию для определения правильности и безопасности исполняемого кода.
- Аргумент обычно предоставляется в виде строки, значение которой может быть неизвестно до момента выполнения. Эта строка должна быть либо скомпилирована во время выполнения программы (с использованием JIT-компиляции ), либо оценена путем интерпретации , что приводит к некоторым дополнительным накладным расходам во время выполнения и обычно генерирует менее эффективный код.
Объекты [ править ]
В объектно-ориентированных языках программирования, которые не поддерживают функции высшего порядка, объекты могут быть эффективной заменой. объекта Методы действуют, по сути, как функции, и метод может принимать объекты в качестве параметров и создавать объекты в качестве возвращаемых значений. Однако объекты часто несут дополнительные накладные расходы во время выполнения по сравнению с чистыми функциями, а также дополнительный шаблонный код для определения и создания экземпляра объекта и его метода(ов). Языки, которые допускают использование на основе стека (а не кучи объектов или структур ), могут обеспечить большую гибкость с помощью этого метода.
Пример использования простой записи на основе стека в Free Pascal с функцией, возвращающей функцию:
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.
Функция a() берет Txy запись в качестве входных данных и возвращает целое значение суммы записей x и y поля (3+7).
Дефункционализация [ править ]
Дефункционализацию можно использовать для реализации функций высшего порядка в языках, в которых отсутствуют функции первого класса :
// 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;
}
В этом случае разные типы используются для запуска разных функций посредством перегрузки функций . Перегруженная функция в этом примере имеет подпись auto apply.
См. также [ править ]
- Первоклассная функция
- Комбинаторная логика
- Программирование на функциональном уровне
- Функциональное программирование
- Каппа-исчисление - формализм функций, исключающий функции высшего порядка.
- Паттерн стратегии
- Сообщения высшего порядка
Ссылки [ править ]
- ^ «PHP: Функции стрелок — Руководство» . www.php.net . Проверено 1 марта 2021 г.