Função de ordem superior - Higher-order function

Em matemática e ciência da computação , uma função de ordem superior é uma função que faz pelo menos uma das seguintes opções:

leva uma ou mais funções como argumentos (ou seja , parâmetros procedimentais ),
retorna uma função como seu resultado.

Todas as outras funções são funções de primeira ordem . Em matemática, funções de ordem superior também são chamadas de operadores ou funcionais . O operador diferencial em cálculo é um exemplo comum, pois mapeia uma função para sua derivada , também uma função. As funções de ordem superior não devem ser confundidas com outros usos da palavra "functor" em toda a matemática, consulte Functor (desambiguação) .

No cálculo lambda não tipado , todas as funções são de ordem superior; em um cálculo lambda digitado , do qual a maioria das linguagens de programação funcionais são derivadas, as funções de ordem superior que tomam uma função como argumento são valores com tipos da forma . ${\ displaystyle (\ tau _ {1} \ to \ tau _ {2}) \ to \ tau _ {3}}$

Exemplos gerais

mapfunção, encontrada em muitas linguagens de programação funcional, é um exemplo de uma função de ordem superior. Ele toma como argumentos uma função f e uma coleção de elementos e, como resultado, retorna uma nova coleção com f aplicada a cada elemento da coleção.
Funções de classificação, que usam uma função de comparação como parâmetro, permitindo ao programador separar o algoritmo de classificação das comparações dos itens sendo classificados. A função padrão C é um exemplo disso. qsort
filtro
dobrar
Aplique
Composição de funções
Integração
Ligar de volta
Travessia de árvore
A gramática de Montague , uma teoria semântica da linguagem natural, usa funções de ordem superior

Suporte em linguagens de programação

Suporte direto

Os exemplos não pretendem comparar e contrastar linguagens de programação, mas servir como exemplos de sintaxe de função de ordem superior

Nos exemplos a seguir, a função de ordem superior twicepega uma função e aplica a função a algum valor duas vezes. Se twicetiver que ser aplicado várias vezes para o mesmo f, preferencialmente deve retornar uma função ao invés de um valor. Isso está de acordo com o princípio " não se repita ".

APL

      twice←{⍺⍺ ⍺⍺ ⍵}

      plusthree←{⍵+3}

      g←{plusthree twice ⍵}
    
      g 7
13

Ou de forma tácita:

      twice←⍣2

      plusthree←+∘3

      g←plusthree twice
    
      g 7
13

C ++

Usando std::functionem 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
}

Ou, com lambdas genéricos fornecidos pelo 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 #

Usando apenas delegados:

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

Ou, de forma equivalente, com métodos estáticos:

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 Markup Language (CFML)

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

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

g = twice(plusThree);

writeOutput(g(7)); // 13

Lisp Comum

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

Dardo

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

No Elixir, você pode misturar definições de módulo e funções anônimas

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

Alternativamente, também podemos compor usando funções anônimas puras.

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

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

Neste exemplo Erlang, a função de ordem superior or_else/2recebe uma lista de funções ( Fs) e argumento ( X). Ele avalia a função Fcom o argumento Xcomo argumento. Se a função Fretornar falso, a próxima função em Fsserá avaliada. Se a função Fretornar {false, Y}, a próxima função Fscom argumento Yserá avaliada. Se a função Fretornar, Ra função de ordem superior or_else/2retornará R. Observe que X, Ye Rpodem ser funções. O exemplo retorna false.

F #

let twice f = f >> f

let plus_three = (+) 3

let g = twice plus_three

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

Ir

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
}

Observe que um literal de função pode ser definido com um identificador ( twice) ou anonimamente (atribuído à variável plusThree).

Haskell

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

Explicitamente,

   twice=.     adverb : 'u u y'

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

ou tacitamente,

   twice=. ^:2

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

Java (1.8+)

Usando apenas interfaces funcionais:

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

Ou, de forma equivalente, com métodos estáticos:

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

Julia

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

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 = @inner

    function val = inner(x)
        val = f(f(x));
    end
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

ou com todas as funções em variáveis:

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

Observe que as funções de seta capturam implicitamente todas as variáveis que vêm do escopo pai, enquanto as funções anônimas exigem que a usepalavra-chave faça o mesmo.

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

ou com todas as funções em variáveis:

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

Pitão

>>> def twice(f):
...     def result(x):
...         return f(f(x))
...     return result

>>> plusthree = lambda i: i + 3

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

A sintaxe do decorador Python costuma ser usada para substituir uma função pelo resultado da passagem dessa função por uma função de ordem superior. Por exemplo, a função gpode ser implementada de forma equivalente:

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

Raku

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

No Raku, todos os objetos de código são fechamentos e, portanto, podem fazer referência a variáveis "lexicais" internas de um escopo externo porque a variável lexical é "fechada" dentro da função. Raku também suporta a sintaxe de "bloco pontudo" para expressões lambda que podem ser atribuídas a uma variável ou chamadas anonimamente.

Rubi

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

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

g = twice(plus_three)

puts g.call(7) # 13

Ferrugem

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

Esquema

(define (add x y) (+ x y))
(define (f x)
  (lambda (y) (+ x y)))
(display ((f 3) 7))
(display (add 3 7))

Neste exemplo de esquema, a função de ordem superior (f x)é usada para implementar currying . Leva um único argumento e retorna uma função. A avaliação da expressão ((f 3) 7)primeiro retorna uma função após a avaliação (f 3). A função retornada é (lambda (y) (+ 3 y)). Em seguida, ele avalia a função retornada com 7 como argumento, retornando 10. Isso é equivalente à expressão (add 3 7), pois (f x)é equivalente à forma curry de (add x y).

Rápido

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 usa o comando apply para aplicar uma função anônima (desde 8.6).

XACML

O padrão XACML define funções de ordem superior no padrão para aplicar uma função a vários valores de pacotes de atributos.

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

A lista de funções de ordem superior em XACML pode ser encontrada aqui .

XQuery

declare function local:twice($f, $x) {
  $f($f($x))
};

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

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

Alternativas

Ponteiros de função

Ponteiros de função em linguagens como C , C ++ e Pascal permitem que os programadores passem referências a funções. O código C a seguir calcula uma aproximação da integral de uma função arbitrária:

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

A função qsort da biblioteca padrão C usa um ponteiro de função para emular o comportamento de uma função de ordem superior.

Macros

As macros também podem ser usadas para obter alguns dos efeitos das funções de ordem superior. No entanto, as macros não podem evitar facilmente o problema de captura de variável; eles também podem resultar em grandes quantidades de código duplicado, o que pode ser mais difícil para um compilador otimizar. Geralmente, as macros não são fortemente tipadas, embora possam produzir código fortemente tipado.

Avaliação de código dinâmico

Em outras linguagens de programação imperativas , é possível obter alguns dos mesmos resultados algorítmicos que são obtidos por meio de funções de ordem superior executando código dinamicamente (às vezes chamado de operações Eval ou Execute ) no escopo da avaliação. Pode haver desvantagens significativas para esta abordagem:

O código do argumento a ser executado geralmente não é digitado estaticamente ; essas linguagens geralmente dependem de tipagem dinâmica para determinar a boa formação e segurança do código a ser executado.
O argumento geralmente é fornecido como uma string, cujo valor pode não ser conhecido até o tempo de execução. Esta string deve ser compilada durante a execução do programa (usando compilação just-in-time ) ou avaliada por interpretação , causando alguma sobrecarga adicional em tempo de execução e geralmente gerando código menos eficiente.

Objetos

Em linguagens de programação orientadas a objetos que não oferecem suporte a funções de ordem superior, os objetos podem ser um substituto eficaz. Os métodos de um objeto atuam em essência como funções, e um método pode aceitar objetos como parâmetros e produzir objetos como valores de retorno. Objetos geralmente carregam sobrecarga de tempo de execução adicional em comparação com funções puras, no entanto, e código clichê adicionado para definir e instanciar um objeto e seu (s) método (s). As linguagens que permitem objetos ou estruturas baseados em pilha (versus baseados em heap ) podem fornecer mais flexibilidade com esse método.

Um exemplo de uso de um registro simples baseado em pilha em Free Pascal com uma função que retorna uma função:

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 função a()recebe um Txyregistro como entrada e retorna o valor inteiro da soma dos campos xe do registro y(3 + 7).

Desfuncionalização

A desfuncionalização pode ser usada para implementar funções de ordem superior em linguagens que não possuem funções de primeira classe :

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

Nesse caso, tipos diferentes são usados para acionar funções diferentes por meio de sobrecarga de função . A função sobrecarregada neste exemplo possui a assinatura auto apply.

Veja também

Função de primeira classe
Lógica combinatória
Programação em nível de função
Programação funcional
Cálculo Kappa - um formalismo para funções que exclui funções de ordem superior
Padrão de estratégia
Mensagens de ordem superior

Languages

In other projects