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

Не путать с Функтором (теорией категорий) .

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

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

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

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

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

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

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

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

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

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

АПЛ

Дополнительная информация: APL (язык программирования).

      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
}

С#

Дополнительная информация: C Sharp (язык программирования).

Использование только делегатов:

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

Кложур

Дополнительная информация: Clojure.

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

Дополнительная информация: Язык разметки ColdFusion.

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

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

g = twice(plusThree);

writeOutput(g(7)); // 13

Общий Лисп

Дополнительная информация: 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 (язык программирования).

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
}

Дарт

Дополнительная информация: Dart (язык программирования).

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

Эрланг

Дополнительная информация: 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).

В этом примере 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.

Ф#

Дополнительная информация: F Sharp (язык программирования).

let twice f = f >> f

let plus_three = (+) 3

let g = twice plus_three

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

Идти

Дополнительная информация: Go (язык программирования).

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

Дж

Дополнительная информация: J (язык программирования).

Явно,

   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

Ява (1.8+)

Дополнительная информация: Java (язык программирования) и история версий Java.

Использование только функциональных интерфейсов:

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

Дополнительная информация: 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
}

Два

Дополнительная информация: 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 = @(x) f(f(x));
end

plusthree = @(i) i + 3;

g = twice(plusthree)

disp(g(7)); % 13

OCaml

Дополнительная информация: 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.

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

Обратите внимание, что стрелочные функции неявно захватывают любые переменные, поступающие из родительской области видимости. тогда как анонимные функции требуют 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

Питон

Дополнительная информация: Python (язык программирования).

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

Р

Дополнительная информация: R (язык программирования).

twice <- function(f) {
  return(function(x) {
    f(f(x))
  })
}

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

g <- twice(plusThree)

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

Раку

Дополнительная информация: Раку (язык программирования).

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 также поддерживает синтаксис «заостренного блока» для лямбда-выражений, которые можно назначать переменной или вызывать анонимно.

Руби

Дополнительная информация: Ruby (язык программирования).

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

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

g = twice(plus_three)

puts g.call(7) # 13

Ржавчина

Дополнительная информация: Rust (язык программирования).

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

Схема

Дополнительная информация: Схема (язык программирования).

(define (compose f g) 
  (lambda (x) (f (g x))))

(define (twice f) 
  (compose f f))

(define (plus-three i)
  (+ i 3))

(define g (twice plus-three))

(display (g 7)) ; 13
(display "\n")

Быстрый

Дополнительная информация: Swift (язык программирования).

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 использует команду Apply для применения анонимной функции (начиная с версии 8.6).

ХАКМЛ

Дополнительная информация: XACML.

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

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

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

XQuery

Дополнительная информация: 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.

См. также

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