WikiDer > Функция высшего порядка - Википедия

Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Сентябрь 2013) (Узнайте, как и когда удалить этот шаблон сообщения)

В математика и Информатика, а функция высшего порядка это функция который выполняет хотя бы одно из следующих действий:

• принимает одну или несколько функций в качестве аргументов (т.е. процедурные параметры),
• возвращает функцию в качестве своего результата.

Все остальные функции функции первого порядка. В математике функции высшего порядка также называют операторы или же функционалы. В дифференциальный оператор в исчисление является распространенным примером, поскольку он отображает функцию на ее производная, также функция. Функции высшего порядка не следует путать с другими видами использования слова «функтор» в математике, см. Функтор (значения).

В нетипизированном лямбда-исчисление, все функции высшего порядка; в типизированное лямбда-исчисление, из которых большинство функциональное программирование языки являются производными, функции более высокого порядка, которые принимают одну функцию в качестве аргумента, являются значениями с типами формы ${ Displaystyle ( тау _ {1} к тау _ {2}) к тау _ {3}}$.

Общие примеры

• карта Функция, встречающаяся во многих языках функционального программирования, является одним из примеров функции высшего порядка. Он принимает в качестве аргументов функцию ж и коллекцию элементов, и в результате возвращает новую коллекцию с ж применяется к каждому элементу из коллекции.
• Функции сортировки, которые принимают функцию сравнения в качестве параметра, что позволяет программисту отделить алгоритм сортировки от сравнений сортируемых элементов. В C стандарт функция qsort является примером этого.
• фильтр
• складывать
• подать заявление
• Состав функций
• Интеграция
• Перезвоните
• Обход дерева
• Грамматика Монтегю, семантическая теория естественного языка, использует функции высшего порядка

Поддержка языков программирования

Было предложено, чтобы эта статья была расколоть в новую статью под названием Сравнение языков программирования (функции высшего порядка). (Обсуждать) (Май 2016)

Прямая поддержка

Примеры не предназначены для сравнения и противопоставления языков программирования, а служат в качестве примеров синтаксиса функций высшего порядка.

В следующих примерах функция высшего порядка дважды принимает функцию и дважды применяет ее к некоторому значению. Если дважды должен применяться несколько раз для одного и того же ж он предпочтительно должен возвращать функцию, а не значение. Это соответствует "не повторяйся"принцип.

OCAML

Явно

позволять add3 Икс = Икс + 3позволять дважды ж Икс = ж (ж Икс)print_int (дважды add3 7) (* 13 *)

Одна линия

print_int ((весело ж Икс -> ж (ж Икс)) ((+)3) 7) (* 13 *)

APL

      дважды←{⍺⍺ ⍺⍺ ⍵}      плюстри←{⍵+3}      грамм←{плюстри дважды ⍵}          грамм 713

Или молчаливо:

      дважды←⍣2      плюстри←+∘3      грамм←плюстри дважды          грамм 713

J

Ясно,

   дважды=.     наречие : 'u u y'   плюстри=. глагол   : 'y + 3'      грамм=. плюстри дважды      грамм 713

или молчаливо,

   дважды=. ^:2   плюстри=. +&3      грамм=. плюстри дважды      грамм 713

или безточечный стиль,

   +&3(^:2) 713

Python

>>> def дважды(ж):...     def результат(а):...         возвращаться ж(ж(а))...     возвращаться результат>>> плюстри = лямбда Икс: Икс + 3>>> грамм = дважды(плюстри)>>> грамм(7)13

Синтаксис декоратора Python часто используется для замены функции результатом передачи этой функции через функцию более высокого порядка. Например, функция грамм может быть реализовано эквивалентно:

>>> @дважды... def грамм(Икс):...     возвращаться Икс + 3>>> грамм(7)13

Язык Wolfram Language

В[1]:=Гнездо[#+3&,7,2]Из[1]:=13

Паскаль

 1{$ mode objfpc} 2 3тип весело = функция(Икс: Целое число): Целое число; 4 5функция add3(Икс: Целое число): Целое число; 6начинать 7  результат := Икс + 3; 8конец; 910функция дважды(func: весело; Икс: Целое число): Целое число;11начинать12  результат := func(func(Икс));13конец;1415начинать16  Writeln(дважды(@add3, 7)); { 13 }17конец.

F #

позволять дважды ж = ж >> жпозволять ж = (+) 3дважды ж 7 |> printf "% A" // 13

D

int делегировать(int) дважды(int делегировать(int) ж){    int дважды(int Икс)    {        возвращаться ж(ж(Икс));    }    возвращаться &дважды;}импорт стандартное.stdio;int плюсТри(int Икс){    возвращаться Икс + 3;}Writeln(дважды(&плюсТри)(7)); // 13

C #

Func<Func<int, int>, int> дважды = ж => Икс => ж(ж(Икс));Func<int, int> плюсТри = Икс => Икс + 3;Консоль.WriteLine(дважды(плюсТри)(7)); // 13

Haskell

дважды :: (а -> а) -> (а -> а)дважды ж = ж . жж :: Num а => а -> аж = вычесть 3главный :: IO ()главный = Распечатать (дважды ж 7) -- 1

Или быстрее:

дважды ж = ж . жглавный = Распечатать $ дважды (+3) 7 -- 13

Clojure

(defn дважды [функция Икс]  (функция (функция Икс)))(дважды #(+ % 3) 7) ;13

В Clojure «#» запускает лямбда-выражение, а «%» относится к следующему аргументу функции.

Схема

(определять (Добавить Икс у) (+ Икс у))(определять (ж Икс)  (лямбда (у) (+ Икс у)))(отображать ((ж 3) 7))(отображать (Добавить 3 7))

В этом примере схемы функция высшего порядка (f x) используется для реализации карри. Он принимает единственный аргумент и возвращает функцию. Оценка выражения ((f 3) 7) сначала возвращает функцию после оценки (ж 3). Возвращенная функция (лямбда (y) (+ 3 y)). Затем он оценивает возвращенную функцию с 7 в качестве аргумента, возвращая 10. Это эквивалентно выражению (прибавить 3 7), поскольку (f x) эквивалентно карри-форме (добавить x y).

Erlang

or_else([], _) -> ложный;or_else([F | Фс], Икс) -> or_else(Фс, Икс, F(Икс)).or_else(Фс, Икс, ложный) -> or_else(Фс, Икс);or_else(Фс, _, {ложный, Y}) -> or_else(Фс, Y);or_else(_, _, р) -> р.or_else([весело эрланг:is_integer/1, весело эрланг:is_atom/1, весело эрланг:is_list/1],3.23).

В этом примере Erlang функция высшего порядка or_else/ 2 принимает список функций (Фс) и аргумент (Икс). Он оценивает функцию F с аргументом Икс как аргумент. Если функция F возвращает false, затем следующая функция в Фс будут оценены. Если функция F возвращается {false, Y} затем следующая функция в Фс с аргументом Y будут оценены. Если функция F возвращается р функция высшего порядка or_else/ 2 вернется р. Обратите внимание, что Икс, Y, и р могут быть функциями. Пример возвращает ложный.

Эликсир

В Elixir вы можете смешивать определения модулей и анонимные функции

defmodule Прыгать делать    def дважды(ж, v) делать        ж.(ж.(v))    конецконецadd3 = fn(v) -> 3 + v конецIO.ставит Прыгать.дважды(add3, 7) #13

В качестве альтернативы мы также можем составлять, используя чистые анонимные функции.

дважды = fn(ж, v) -> ж.(ж.(v)) конецadd3 = fn(v) -> 3 + v конецIO.ставит дважды.(add3, 7) #13

JavaScript

const дважды = (ж, v) => ж(ж(v));const add3 = v => v + 3;дважды(add3, 7); // 13

Идти

func дважды(ж func(int) int, v int) int {	возвращаться ж(ж(v))}func главный() {	ж := func(v int) int {		возвращаться v + 3	}	дважды(ж, 7) // возвращает 13}

Обратите внимание, что функциональный литерал может быть определен с помощью идентификатора (дважды) или анонимно (присваивается переменной ж). Запустить полную программу на Перейти на игровую площадку.

Scala

def дважды(ж:Int=>Int) = ж сочинять ждважды(_+3)(7) // 13

Java (1.8+)

Функция<IntUnaryOperator, IntUnaryOperator> дважды = ж -> ж.а потом(ж);дважды.подать заявление(Икс -> Икс + 3).applyAsInt(7); // 13

Юля

Юлия> функция дважды(ж)           функция результат(а)               возвращаться ж(ж(а))               конец           возвращаться результат       конецдважды (общая функция с 1 методом)Юлия> плюстри(Икс) = Икс + 3plusthree (общая функция с 1 методом)Юлия> грамм = дважды(плюстри)(:: var "# result # 3" {typeof (plusthree)}) (общая функция с 1 методом)Юлия> грамм(7)13

Котлин

весело <Т> дважды(ж: (Т)->Т): (Т)->Т = {ж(ж(Это))}весело ж(Икс:Int) = Икс + 3println(дважды(::ж)(7)) // 13

Lua

местный дважды = функция(ж,v)  возвращаться ж(ж(v))конецместный добавитьтри = функция(v)  возвращаться v + 3конецРаспечатать(дважды(добавитьтри,7)) -- 13

MATLAB

функциярезультат =дважды(fnhandle, v)результат = fnhandle(fnhandle(v));конецдобавитьтри = @(п) п + 3;дисп(дважды(добавитьтри, 7)); % 13

Быстрый

// универсальная функцияfunc дважды<Т>(_ v: @побег (Т) -> Т) -> (Т) -> Т {    возвращаться { v(v($0)) }}// предполагаемое закрытиепозволять ж = { $0 + 3 }дважды(ж)(10) // 16

Ржавчина

// Возьмем функцию f (x), вернем функцию f (f (x))fn дважды<А>(функция: импFn(А)-> А)-> импFn(А)-> А{двигаться|а|функция(функция(а))}// Возвращаем x + 3fn плюстри(Икс: i32)-> i32 {Икс+3}fn главный(){позволятьграмм=дважды(плюстри);println!("{}",грамм(7));}

Рубин

def дважды(ж, Икс)  ж.вызов ж.вызов(Икс)конецadd3 = ->(Икс) { Икс + 3 }ставит дважды(add3, 7) #=> 13

C

С указателями функций в C:

#включают <stdio.h>typedef int (*int_func_int) (int);int add3(int Икс) {	возвращаться Икс + 3;}int дважды(int_func_int ж, int v) {	возвращаться ж(ж(v));}int главный() {	printf("% d п", 		дважды(add3, 7)	);		возвращаться 0;}

C ++

С общими лямбдами, предоставляемыми C ++ 14:

#включают <iostream>авто дважды = [](авто ж, int v){    возвращаться ж(ж(v));};    авто ж = [](int я){    возвращаться я + 3;}; int главный(){       стандартное::cout << дважды(ж, 7) << стандартное::конец;}

Или, используя std :: function в C ++ 11:

#включают <iostream>#включают <functional>авто дважды = [](const стандартное::функция<int(int)>& ж, int v){    возвращаться ж(ж(v));};    авто ж = [](int я){    возвращаться я + 3;};    int главный(){    стандартное::cout << дважды(ж, 7) << стандартное::конец;}

D

импорт стандартное.stdio : Writeln;псевдоним дважды = (ж, я) => ж(ж(я));псевдоним ж = (int я) => я + 3;пустота главный(){    Writeln(дважды(ж, 7));}

Язык разметки ColdFusion (CFML)

дважды = функция(ж, v) {    возвращаться ж(ж(v));};ж = функция(v) {    возвращаться v + 3;};writeOutput(дважды(ж, 7)); // 13

PHP

$ дважды = fn (Закрытие $ f, int $ v): int => $ f($ f($ v));$ f = fn (int $ v): int => $ v + 3;эхо $ дважды($ f, 7); // 13

р

дважды <- функция(func) {  возвращаться(функция(Икс) {    func(func(Икс))  })}ж <- функция(Икс) {  возвращаться(Икс + 3)}грамм <- дважды(ж)> Распечатать(грамм(7))[1] 13

Perl

суб add3 {    мой ($ x) = @_;    $ x + 3;}суб дважды {    мой ($ f) = @_;    суб {        $ f->($ f->(@_));    };}сказать дважды(\&add3)->(7); # 13

или со всеми функциями в переменных:

мой $ add3 = суб {    мой ($ x) = @_;    $ x + 3;};мой $ дважды = суб {    мой ($ f) = @_;    суб {        $ f->($ f->(@_));    };};мой $ г = $ дважды->($ add3);сказать $ г->(7); # 13

Раку

суб дважды(Вызываемый: D $ c) {    возвращаться суб { $ c($ c($ ^ x)) };}суб ж(Инт: D $ x) {    возвращаться $ x + 3;}мой $ г = дважды(& е);сказать $ г(7); # ВЫХОД: 13

В Raku все объекты кода являются замыканиями и, следовательно, могут ссылаться на внутренние «лексические» переменные из внешней области видимости, поскольку лексическая переменная «закрыта» внутри функции. Perl 6 также поддерживает синтаксис «заостренного блока» для лямбда-выражений, которые можно назначать переменной или вызывать анонимно.

Tcl

набор дважды {{ж v} {подать заявление $ f [подать заявление $ f $ v]}}набор ж {{v} {возвращаться [выражение $ v + 3]}}# результат: 13ставит [подать заявление $ дважды $ f 7]

Tcl использует команду apply для применения анонимной функции (начиная с 8.6).

XQuery

объявить функция местный: дважды($ж, $Икс) {  $ж($ж($Икс))};объявить функция местный: f($Икс) {  $Икс + 3};местный: дважды(местный: f#1, 7) (: 13 :)

XACML

Стандарт XACML определяет в стандарте функции высшего порядка для применения функции к нескольким значениям пакетов атрибутов.

правило allowEntry{    разрешать    условие anyOfAny (функция[stringEqual], гражданство, разрешено)}

Список функций высшего порядка в XACML можно найти здесь.

Альтернативы

Указатели на функции

Указатели на функции на таких языках, как C и C ++ позволяют программистам передавать ссылки на функции. Следующий код C вычисляет приближение интеграла произвольной функции:

#включают <stdio.h>двойной квадрат(двойной Икс){    возвращаться Икс * Икс;}двойной куб(двойной Икс){    возвращаться Икс * Икс * Икс;}/ * Вычислить интеграл от f () в интервале [a, b] * /двойной интеграл(двойной ж(двойной Икс), двойной а, двойной б, int п){    int я;    двойной сумма = 0;    двойной dt = (б - а) / п;    за (я = 0;  я < п;  ++я) {        сумма += ж(а + (я + 0.5) * dt);    }    возвращаться сумма * dt;}int главный(){    printf("%грамм п", интеграл(квадрат, 0, 1, 100));    printf("%грамм п", интеграл(куб, 0, 1, 100));    возвращаться 0;}

В qsort функция из стандартной библиотеки C использует указатель функции для имитации поведения функции высшего порядка.

Макросы

Макросы также может использоваться для достижения некоторых эффектов функций высшего порядка. Однако с помощью макросов нелегко избежать проблемы захвата переменных; они также могут привести к появлению большого количества дублированного кода, что может быть труднее оптимизировать компилятору. Макросы, как правило, не являются строго типизированными, хотя они могут создавать строго типизированный код.

Оценка динамического кода

В другом императивное программирование языков, можно достичь некоторых из тех же алгоритмических результатов, которые получаются с помощью функций более высокого порядка путем динамического выполнения кода (иногда называемого Eval или же Выполнять операций) в рамках оценки. У такого подхода могут быть существенные недостатки:

• Код аргумента, который должен быть выполнен, обычно не статически типизированный; эти языки обычно полагаются на динамическая типизация для определения правильности и безопасности кода, который будет выполняться.
• Аргумент обычно предоставляется в виде строки, значение которой может быть неизвестно до времени выполнения. Эта строка должна быть либо скомпилирована во время выполнения программы (используя своевременная компиляция) или оценивается интерпретация, вызывая дополнительные накладные расходы во время выполнения и обычно генерируя менее эффективный код.

Объекты

В объектно-ориентированного программирования языки, которые не поддерживают функции высшего порядка, объекты может быть эффективной заменой. Объект методы действуют по существу как функции, и метод может принимать объекты как параметры и создавать объекты как возвращаемые значения. Однако объекты часто несут дополнительные накладные расходы времени выполнения по сравнению с чистыми функциями, и шаблонный код для определения и создания экземпляра объекта и его метода (ов). Языки, которые позволяют кучана основе (по сравнению с кучана основе) объектов или структуры может обеспечить большую гибкость с помощью этого метода.

Пример использования простой записи на основе стека в Free Pascal с функцией, которая возвращает функцию:

программа пример;тип   int = целое число;  Txy = записывать Икс, у: int; конец;  Tf = функция (ху: Txy): int;     функция ж(ху: Txy): int; начинать   Результат := ху.у + ху.Икс; конец;функция грамм(func: Tf): Tf; начинать   результат := func; конец;вар   а: Tf;  ху: Txy = (Икс: 3; у: 7);начинать    а := грамм(@ж);     // возвращаем функцию в "а"  Writeln(а(ху)); // выводит 10конец.

Функция а () занимает Txy запись в качестве входных данных и возвращает целочисленное значение суммы Икс и у поля (3 + 7).

Дефункционализация

Дефункционализация может использоваться для реализации функций высшего порядка на языках, в которых отсутствует первоклассные функции:

// Структуры данных дефункционализированной функциишаблон<typename Т> структура Добавлять { Т ценить; };шаблон<typename Т> структура DivBy { Т ценить; };шаблон<typename F, typename грамм> структура Сочинение { F ж; грамм грамм; };// Реализации приложения с дефункциональной функциейшаблон<typename F, typename грамм, typename Икс>авто подать заявление(Сочинение<F, грамм> ж, Икс аргумент) {    возвращаться подать заявление(ж.ж, подать заявление(ж.грамм, аргумент));}шаблон<typename Т, typename Икс>авто подать заявление(Добавлять<Т> ж, Икс аргумент) {    возвращаться аргумент  + ж.ценить;}шаблон<typename Т, typename Икс>авто подать заявление(DivBy<Т> ж, Икс аргумент) {    возвращаться аргумент / ж.ценить;}// Функция компоновки высшего порядкашаблон<typename F, typename грамм>Сочинение<F, грамм> сочинять(F ж, грамм грамм) {    возвращаться Сочинение<F, грамм> {ж, грамм};}int главный(int argc, const char* argv[]) {    авто ж = сочинять(DivBy<плавать>{ 2.0f }, Добавлять<int>{ 5 });    подать заявление(ж, 3); // 4.0f    подать заявление(ж, 9); // 7.0f    возвращаться 0;}

В этом случае используются разные типы для запуска разных функций через перегрузка функции. Перегруженная функция в этом примере имеет подпись автоматически применять.

Смотрите также

• Первоклассная функция
• Комбинаторная логика
• Программирование на функциональном уровне
• Функциональное программирование
• Исчисление каппа - формализм для функций, которые исключает функции высшего порядка
• Шаблон стратегии
• Сообщения высшего порядка

Рекомендации