Функция высшего порядка
 | Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( сентябрь 2013 г. ) |
В математике и информатике функция высшего порядка ( HOF ) — это функция , которая выполняет хотя бы одно из следующих действий:
- принимает в качестве аргументов одну или несколько функций (т. е. процедурный параметр , который является параметром процедуры , которая сама является процедурой),
- возвращает функцию в качестве результата.
Все остальные функции являются функциями первого порядка . В математике функции высшего порядка также называются операторами или функционалами . Дифференциальный оператор в исчислении является распространенным примером, поскольку он отображает функцию в ее производную , которая также является функцией. Функции высшего порядка не следует путать с другими значениями слова «функтор» в математике, см. Функтор (значения) .
В нетипизированном лямбда-исчислении все функции имеют более высокий порядок; в типизированном лямбда-исчислении , от которого произошло большинство функциональных языков программирования, функции высшего порядка, принимающие одну функцию в качестве аргумента, представляют собой значения с типами вида .
Общие примеры [ править ]
mapФункция, встречающаяся во многих языках функционального программирования, является одним из примеров функции высшего порядка. В качестве аргументов он принимает функцию f и коллекцию элементов и в результате возвращает новую коллекцию, в которой f применяется к каждому элементу коллекции.- Функции сортировки, которые принимают функцию сравнения в качестве параметра, что позволяет программисту отделить алгоритм сортировки от сравнения сортируемых элементов. Стандартная C функция
qsortявляется примером этого. - фильтр
- складывать
- применять
- Функциональная композиция
- Интеграция
- Перезвонить
- Обход дерева
- Грамматика Монтегю , семантическая теория естественного языка, использует функции высшего порядка.
Поддержка языков программирования [ править ]
Прямая поддержка [ править ]
Эти примеры не предназначены для сравнения и противопоставления языков программирования, а служат примерами синтаксиса функций высшего порядка.
В следующих примерах функция высшего порядка twiceпринимает функцию и дважды применяет ее к некоторому значению. Если twice необходимо применять несколько раз для одного и того же fжелательно, чтобы он возвращал функцию, а не значение. Это соответствует принципу « не повторяйся ».
АПЛ [ править ]
дважды ← { ⍺⍺ ⍺⍺ ⍵ }
плюстри ← { ⍵ + 3 }
г ← { плюстри дважды ⍵ }
г 7
13
Или молчаливо:
twice ← ⍣ 2
plusthree ← + ∘ 3
g ← plusthree twice
g 7
13
С++ [ править ]
С использованием std::function в С++11 :
#include <iostream>
#include <functional>
auto дважды = []( 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 = дважды ( plus_three );
std :: cout << g ( 7 ) << '\n' ; // 13
}
Или с помощью общих лямбда-выражений, предоставляемых C++14:
#include <iostream>
auto дважды = []( const auto & f )
{
return [ f ] ( int x ) {
return f ( f ( x ));
};
};
auto plus_three = []( int i )
{
return i + 3 ;
};
int main ()
{
auto g = дважды ( plus_three );
std :: cout << g ( 7 ) << '\n' ; // 13
}
С# [ править ]
Использование только делегатов:
используя систему ;
public class Program
{
public static void Main ( string [] args )
{
Func < Func < int , int > , Func < int , int >> дважды = f => x => f ( f ( x ));
Func < int , int > plusThree = i => i + 3 ;
вар г = дважды ( плюсТри );
Консоль . WriteLine ( г ( 7 )); // 13
}
}
Или, что то же самое, со статическими методами:
используя систему ;
public class Program
{
private static Func < int , int > Twice ( Func < int , int > f )
{
return x => f ( f ( x ));
}
Private static int PlusThree ( int i ) => я + 3 ;
public static void Main ( string [] args )
{
var g = Twice ( PlusThree );
Консоль . WriteLine ( г ( 7 )); // 13
}
}
Кложур [ править ]
( defn дважды [ f ]
( fn [ x ] ( f ( f x ))))
( defn плюс три [ i ]
( + i 3 ))
( def g ( дважды плюс три ))
( println ( g 7 ) ) ; 13
Язык разметки ColdFusion (CFML) [ править ]
дважды = функция ( f ) {
return function ( x ) {
return f ( f ( x ));
};
};
plusThree = функция ( я ) {
возвращение я + 3 ;
};
г = дважды ( плюсТри );
writeOutput ( г ( 7 )); // 13
Общий Лисп [ править ]
( defun дважды ( f )
( лямбда ( x ) ( funcall f ( funcall f x ))))
( defun плюс три ( i )
( + i 3 ))
( defvar g ( дважды #' плюс три ))
( print ( вызов функции г 7 ))
Д [ править ]
импорт стандартный . stdio : writeln ;
псевдоним дважды = ( f ) => ( int x ) => f ( f ( x ));
псевдоним plusThree = ( int i ) => я + 3 ;
void main ()
{
auto g = дважды ( plusThree );
writeln ( г ( 7 )); // 13
}
Dart[editдартс
int Function ( int ) дважды ( int Function ( int ) f ) {
return ( x ) {
return f ( f ( x ));
};
}
int plusThree ( int i ) {
return i + 3 ;
}
void main () {
Final g = дважды ( plusThree );
распечатать ( г ( 7 )); // 13
}
Elixir[editЭликсир
В Elixir вы можете смешивать определения модулей и анонимные функции.
defmodule Hof do
def дважды ( f ) do
fn ( x ) -> f . ( f . ( x )) end
end
end
plus_three = fn ( i ) -> i + 3 end
g = Hof . дважды ( плюс_три )
IO . ставит г. ( 7 ) # 13
В качестве альтернативы мы также можем использовать чистые анонимные функции.
дважды = fn ( f ) ->
fn ( x ) -> f . ( f . ( x )) конец
end
plus_three = fn ( я ) -> я + 3 конец
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 дважды f = f >> f
let plus_three = (+) 3
let g = дважды plus_three
g 7 |> printf "%A" // 13
Иди [ править ]
package main
import " fmt "
func дважды ( f func ( int ) int ) func ( int ) int {
return func ( x int ) int {
return f ( f ( x ))
}
}
func main () {
plusThree := func ( я int ) int {
return i + 3
}
g = дважды ( plusThree )
fmt : Распечатать ( г ( 7 )) /13
}
Обратите внимание, что литерал функции может быть определен либо с помощью идентификатора ( twice) или анонимно (присваивается переменной plusThree).
Хаскелл [ править ]
дважды :: ( Int -> Int ) -> ( Int -> Int )
дважды f = f . f
plusThree :: Int -> Int
plusThree = ( + 3 )
main :: IO ()
main = print ( g 7 ) -- 13
где
g = дважды plusThree
Я говорю ]
Явно,
дважды =. наречие : 'уу й'
плюстри =. глагол : 'y + 3'
g =. плюстри дважды
г 7
13
или молчаливо,
дважды =. ^: 2
плюс три =. +& 3
г =. плюстри дважды
г 7
13
Ява ) 1.8+ (
Использование только функциональных интерфейсов:
импортировать java.util.function.* ;
class Main {
public static void main ( String [] args ) {
Function < IntUnaryOperator , IntUnaryOperator > дважды = f -> f . и Затем ( е );
IntUnaryOperator plusThree = i -> i + 3 ;
вар г = дважды . применить ( плюсТри );
Система . вне . println ( g . applyAsInt ( 7 )); // 13
}
}
Или, что то же самое, со статическими методами:
импортировать java.util.function.* ;
класс Main {
частный статический IntUnaryOperator дважды ( IntUnaryOperator f ) {
return f . и Затем ( е );
}
Private static int plusThree ( int i ) {
return i + 3 ;
}
Public static void main ( String [] args ) {
var g = дважды ( Main :: plusThree );
Система . вне . println ( g . applyAsInt ( 7 )); // 13
}
}
JavaScript [ править ]
С функциями стрелки:
"используйте строгий" ;
const дважды = f => x => f ( f ( x ));
const plusThree = я => я + 3 ;
const g = дважды ( plusThree );
консоль . журнал ( г ( 7 )); // 13
Или с классическим синтаксисом:
"используйте строгий" ;
функция дважды ( f ) {
return function ( x ) {
return f ( f ( x ));
};
}
Функция plusThree ( я ) {
возвращение я + 3 ;
}
Const g = дважды ( plusThree );
консоль . журнал ( г ( 7 )); // 13
Юлия [ править ]
julia> функция дважды ( f )
функции результат ( x )
return f ( f ( x ))
end
return result
end
дважды (универсальная функция с 1 методом)
julia> plusthree ( i ) = i + 3
plusthree (универсальная функция с 1 методом)
julia> g = дважды ( plusthree )
(::var"#result#3"{typeof(plusthree)}) (универсальная функция с 1 методом)
julia> g ( 7 )
13
Котлин [ править ]
fun дважды ( f : ( Int ) -> Int ): ( Int ) -> Int {
return { f ( f ( it )) }
}
fun plusThree ( i : Int ) = i + 3
fun main () {
val g = дважды ( :: plusThree )
println ( g ( 7 )) // 13
}
Луа [ править ]
функция дважды ( f )
return function ( x )
return f ( f ( x ))
end
end
function plusThree ( i )
return i + 3
end
local g = дважды ( plusThree )
print ( g ( 7 )) -- 13
МАТЛАБ [ править ]
функции результат = дважды ( f )
result = @( x ) f ( f ( x ));
конец
плюстри = @( i ) i + 3 ;
g = дважды ( плюстри )
disp ( g ( 7 )); % 13
OCaml [ править ]
let дважды f x =
f ( f x )
let plus_three =
(+) 3
let () =
let g = дважды plus_three в
print_int ( g 7 ); (* 13 *)
print_newline ()
PHP [ править ]
<?php
объявить ( strict_types = 1 );
функция дважды ( вызываемая $f ) : Closure {
return function ( int $x ) use ( $f ) : int {
return $f ( $f ( $x ));
};
}
Функция plusThree ( int $i ) : int {
return $i + 3 ;
}
$g = дважды ( 'plusThree' );
echo $g ( 7 ), " \n " ; // 13
или со всеми функциями в переменных:
<?php
объявить ( strict_types = 1 );
$twice = fn ( вызываемый $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 ключевое слово, чтобы сделать то же самое.
Перл [ править ]
используйте строгий ;
использовать предупреждения ;
суб дважды {
my ( $f ) = @_ ;
sub {
$f -> ( $f -> ( @_ ));
};
}
Sub plusThree {
my ( $i ) = @_ ;
$я + 3 ;
}
мой $g = дважды ( \& plusThree );
напечатайте $g -> ( 7 ), "\n" ; № 13
или со всеми функциями в переменных:
используйте строгий ;
использовать предупреждения ;
мой $twice = sub {
my ( $f ) = @_ ;
sub {
$f -> ( $f -> ( @_ ));
};
};
мой $plusThree = sub {
my ( $i ) = @_ ;
$я + 3 ;
};
мой $g = $twice -> ( $plusThree );
напечатайте $g -> ( 7 ), "\n" ; № 13
Питон [ править ]
>>> def дважды ( f ):
... def result ( x ):
... return f ( f ( x ))
... возвращаем результат
>>> plus_three = лямбда i : i + 3
>>> g = дважды ( плюс_три )
>>> г ( 7 )
13
Синтаксис декоратора Python часто используется для замены функции результатом передачи этой функции через функцию более высокого порядка. Например, функция g может быть реализовано эквивалентно:
>>> @twice
... def g ( i ):
... return i + 3
>>> g ( 7 )
13
Р [ править ]
дважды <- функция ( f ) {
return ( function ( x ) {
f ( f ( x ))
})
}
plusThree <- function ( i ) {
return ( i + 3 )
}
g <- дважды ( plusThree )
> print ( г ( 7 ))
[ 1 ] 13
Раку [ править ]
суб дважды ( Callable:D $f ) {
return sub { $f ( $f ( $^x )) };
}
sub plusThree ( Int:D $i ) {
вернуть $i + 3 ;
}
мой $g = дважды ( &plusThree );
скажите $g ( 7 ); № 13
В Raku все объекты кода являются замыканиями и поэтому могут ссылаться на внутренние «лексические» переменные из внешней области, поскольку лексическая переменная «закрыта» внутри функции. Raku также поддерживает синтаксис «заостренного блока» для лямбда-выражений, которые можно назначать переменной или вызывать анонимно.
Руби [ править ]
def дважды ( ж )
-> ( Икс ) { ж . вызов ( f . вызов ( x )) }
конец
plus_three = -> ( я ) { я + 3 }
g = дважды ( plus_three )
ставит g . позвони ( 7 ) # 13
Ржавчина [ править ]
fn дважды ( f : impl Fn ( i32 ) -> i32 ) -> impl Fn ( i32 ) -> i32 {
move | х | f ( f ( x ))
}
fn plus_three ( i : i32 ) -> i32 {
i + 3
}
fn main () {
let g = дважды ( plus_three );
распечататьлн! ( "{}" , г ( 7 )) // 13
}
Масштаб [ править ]
object Main {
def дважды ( f : Int => Int ): Int => Int =
f compose f
def plusThree ( i : Int ): Int =
i + 3
def main ( args : Array [ String ]): Unit = {
val g = дважды ( plusThree )
print ( g ( 7 )) // 13
}
}
Схема [ править ]
( определить ( дважды f )
( лямбда ( x ) ( f ( f x ))))
( определить ( плюс три i )
( + i 3 ))
( определить g ( дважды плюс три ))
( отобразить ( g 7 ) ) ; 13
( отобразить " \n " )
Свифт [ править ]
func дважды ( _ f : @ экранирование ( Int ) -> Int ) -> ( Int ) -> Int {
return { f ( f ( $0 )) }
}
let plusThree = { $0 + 3 }
let g = дважды ( plusThree )
печать ( г ( 7 )) // 13
ТКЛ [ править ]
set дважды {{ f x } {apply $f [apply $f $x ]}}
set plusThree {{ i } {return [expr $i + 3 ]}}
# результат: 13
puts [apply $twice $plusThree 7 ]
Tcl использует команду Apply для применения анонимной функции (начиная с версии 8.6).
XACML [ править ]
Стандарт XACML определяет в стандарте функции более высокого порядка для применения функции к нескольким значениям пакетов атрибутов.
ruleallowEntry гражданства {
разрешения
условие AnyOfAny(функция [ stringEqual ], гражданство , разрешенные )
}
Список функций высшего порядка в XACML можно найти здесь .
XQuery [ править ]
объявить функцию локально: дважды ( $ f , $ x ) {
$ f ( $ f ( $ x ))
};
объявить функцию 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 ;
}
/* Вычисляем интеграл от f() в интервале [a,b] */
двойной интеграл ( double f ( double x ), double a , double b , int n )
{
int i ;
двойная сумма = 0 ;
двойной dt знак равно ( б - а ) / п ;
для ( я знак равно 0 ; я < п ; ++ я ) {
сумма += ж ( а + ( я + 0,5 ) * dt );
}
вернуть сумму * dt ;
}
int main ()
{
printf ( "%g \n " , интеграл ( квадрат , 0 , 1 , 100 ));
printf ( "%g \n " , целое число ( куб , 0 , 1 , 100 ));
вернуть 0 ;
}
Функция qsort из стандартной библиотеки C использует указатель на функцию для эмуляции поведения функции более высокого порядка.
Макросы [ править ]
Макросы также можно использовать для достижения некоторых эффектов функций более высокого порядка. Однако макросы не могут легко избежать проблемы захвата переменных; они также могут привести к большому количеству дублированного кода, который компилятору может быть сложнее оптимизировать. Макросы, как правило, не являются строго типизированными, хотя они могут создавать строго типизированный код.
Динамическая оценка кода [ править ]
В других императивных языках программирования можно достичь некоторых из тех же алгоритмических результатов, которые получаются с помощью функций более высокого порядка, путем динамического выполнения кода (иногда называемого операциями Eval или Execute ) в области оценки. У такого подхода могут быть существенные недостатки:
- Код аргумента, который должен быть выполнен, обычно не является статически типизированным ; эти языки обычно полагаются на динамическую типизацию для определения правильности и безопасности исполняемого кода.
- Аргумент обычно предоставляется в виде строки, значение которой может быть неизвестно до момента выполнения. Эта строка должна быть либо скомпилирована во время выполнения программы (с использованием JIT-компиляции ), либо оценена путем интерпретации , что приводит к некоторым дополнительным накладным расходам во время выполнения и обычно генерирует менее эффективный код.
Объекты [ править ]
В объектно-ориентированных языках программирования, которые не поддерживают функции высшего порядка, объекты могут быть эффективной заменой. объекта Методы действуют, по сути, как функции, и метод может принимать объекты в качестве параметров и создавать объекты в качестве возвращаемых значений. Однако объекты часто несут дополнительные накладные расходы во время выполнения по сравнению с чистыми функциями, а также дополнительный шаблонный код для определения и создания экземпляра объекта и его метода(ов). Языки, которые допускают использование на основе стека (а не кучи объектов или структур ), могут обеспечить большую гибкость с помощью этого метода.
Пример использования простой записи на основе стека в Free Pascal с функцией, возвращающей функцию:
программы пример ;
введите
int = целое число ;
Txy = запись x , y : int ; конец ;
Tf = функция ( xy : Txy ) : int ;
функция f ( xy : Txy ) : int ;
начало
Результат := xy . у + ху . Икс ;
конец ;
функция g ( func : Tf ) : Tf ;
начать
результат := функция ;
конец ;
вар
а : Тф ;
ху : Txy = ( Икс : 3 ; у : 7 ) ;
начать
а := г ( @ f ) ; // возвращаем функцию в "a"
writeln ( a ( xy )) ; // печатает 10
end .
Функция a() занимает Txy запись в качестве входных данных и возвращает целое значение суммы записей x и y поля (3+7).
Дефункционализация [ править ]
Дефункционализацию можно использовать для реализации функций высшего порядка в языках, в которых отсутствуют функции первого класса :
// Структуры данных дефункциональной функции
template < typename T > struct Add { T value ; };
шаблон < имя типа T > struct DivBy { T значение ; };
шаблон < имя типа F , имя типа G > struct Composition { F f ; Гарантированная победа ; };
// Реализации приложения дефункциональной функции
template < typename F , typename G , typename X >
auto apply ( Composition < F , G > f , X arg ) {
return apply ( f . f , apply ( f . g , arg ));
}
template < типа T , имя X >
автоматическое применение ( Add <T> ) f , arg X f . {
return arg + типа имя ценить ;
}
Шаблон < типа T , имя X >
автоматическое применение ( DivBy <T> ) f , arg X f . {
return arg / типа имя ценить ;
}
функции компоновки высшего порядка
// Шаблон < typename F , typename G >
Compose < 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 });
применить ( f , 3 ); 4.0f
// применить ( f , 9 ); // 7.0f
возвращаем 0 ;
}
В этом случае разные типы используются для запуска разных функций посредством перегрузки функций . Перегруженная функция в этом примере имеет подпись auto apply.
См. также [ править ]
- Первоклассная функция
- Комбинаторная логика
- Программирование на функциональном уровне
- Функциональное программирование
- Каппа-исчисление - формализм функций, исключающий функции высшего порядка.
- Паттерн стратегии
- Сообщения высшего порядка
Ссылки [ править ]
- ^ «PHP: Функции стрелок — Руководство» . www.php.net . Проверено 01 марта 2021 г.