Higher-order function
This article includes a list of references, but its sources remain unclear because it has insufficient inline citations. (September 2013) (Learn how and when to remove this template message) |
In mathematics and computer science, a higher-order function is a function that does at least one of the following:
- takes one or more functions as arguments (i.e. procedural parameters),
- returns a function as its result.
All other functions are first-order functions. In mathematics higher-order functions are also termed operators or functionals. The differential operator in calculus is a common example, since it maps a function to its derivative, also a function. Higher-order functions should not be confused with other uses of the word "functor" throughout mathematics, see Functor (disambiguation).
In the untyped lambda calculus, all functions are higher-order; in a typed lambda calculus, from which most functional programming languages are derived, higher-order functions that take one function as argument are values with types of the form .
Contents
- 1 General examples
- 2 Support in programming languages
- 2.1 Direct support
- 2.1.1 OCAML
- 2.1.2 APL
- 2.1.3 J
- 2.1.4 Python
- 2.1.5 Pascal
- 2.1.6 F#
- 2.1.7 D
- 2.1.8 C#
- 2.1.9 Haskell
- 2.1.10 Clojure
- 2.1.11 Scheme
- 2.1.12 Erlang
- 2.1.13 Elixir
- 2.1.14 JavaScript
- 2.1.15 Go
- 2.1.16 Scala
- 2.1.17 Java (1.8+)
- 2.1.18 Kotlin
- 2.1.19 Lua
- 2.1.20 Swift
- 2.1.21 Rust
- 2.1.22 Ruby
- 2.1.23 C++
- 2.1.24 D
- 2.1.25 ColdFusion Markup Language (CFML)
- 2.1.26 PHP
- 2.1.27 R
- 2.1.28 Perl 6
- 2.1.29 Tcl
- 2.1.30 XQuery
- 2.2 XACML
- 2.3 Alternatives
- 2.1 Direct support
- 3 See also
- 4 References
General examples[edit]
map
function, found in many functional programming languages, is one example of a higher-order function. It takes as arguments a function f and a list of elements, and as the result, returns a new list with f applied to each element from the list.- Sorting functions, which take a comparison function as a parameter, allowing the programmer to separate the sorting algorithm from the comparisons of the items being sorted. The C standard function
qsort
is an example of this. - fold
- Function composition
- Integration
- Callback
- Tree traversal
Support in programming languages[edit]
It has been suggested that this article be split into a new article titled Comparison of programming languages (higher-order functions). (Discuss) (May 2016) |
Direct support[edit]
The examples are not intended to compare and contrast programming languages, but to serve as examples of higher-order function syntax
In the following examples, the higher-order function twice
takes a function, and applies the function to some value twice. If twice
has to be applied several times for the same f
it preferably should return a function rather than a value. This is in line with the "don't repeat yourself" principle.
OCAML[edit]
Explicitly
let add3 x = x + 3
let twice f x = f (f x)
print_int (twice add3 7) (* 13 *)
One-Line
print_int ((fun f x -> f (f x)) ((+)3) 7) (* 13 *)
APL[edit]
twice←{⍺⍺ ⍺⍺ ⍵}
plusthree←{⍵+3}
g←{plusthree twice ⍵}
g 7
13
Or in a tacit manner:
twice←⍣2
plusthree←+∘3
g←plusthree twice
g 7
13
J[edit]
Explicitly,
twice=. adverb : 'u u y'
plusthree=. verb : 'y + 3'
g=. plusthree twice
g 7
13
or tacitly,
twice=. ^:2
plusthree=. +&3
g=. plusthree twice
g 7
13
or point-free style,
+&3(^:2) 7
13
Python[edit]
>>> def twice(f):
... def result(a):
... return f(f(a))
... return result
>>> plusthree = lambda x: x+3
>>> g = twice(plusthree)
>>> g(7)
13
Pascal[edit]
1 {$mode objfpc}
2
3 type fun = function(x: Integer): Integer;
4
5 function add3(x: Integer): Integer;
6 begin
7 result := x + 3;
8 end;
9
10 function twice(func: fun; x: Integer): Integer;
11 begin
12 result := func(func(x));
13 end;
14
15 begin
16 writeln(twice(@add3, 7)); { 13 }
17 end.
F#[edit]
let twice f = f >> f
let f = (+) 3
twice f 7 |> printf "%A" // 13
D[edit]
int delegate(int) twice(int delegate(int) f)
{
int twiceApplied(int x)
{
return f(f(x));
}
return &twiceApplied;
}
import std.stdio;
int plusThree(int x)
{
return x + 3;
}
writeln(twice(&plusThree)(7)); // 13
C#[edit]
Func<Func<int,int>,Func<int,int>> twice = f => x => f(f(x));
Func<int,int> plusThree = x => x + 3;
Console.WriteLine(twice(plusThree)(7)); // 13
or more quickly
var twice = f => x => f(f(x));
var plusThree = x => x + 3;
Console.WriteLine(twice(plusThree)(7)); // 13
Haskell[edit]
twice :: (a -> a) -> (a -> a)
twice f = f . f
f :: Num a => a -> a
f = subtract 3
main :: IO ()
main = print (twice f 7) -- 1
Or more quickly:
twice f = f . f
main = print $ twice (+3) 7 -- 13
Clojure[edit]
(defn twice [function x]
(function (function x)))
(twice #(+ % 3) 7) ;13
In Clojure, "#" starts a lambda expression, and "%" refers to the next function argument.
Scheme[edit]
(define (add x y) (+ x y))
(define (f x)
(lambda (y) (+ x y)))
(display ((f 3) 7))
(display (add 3 7))
In this Scheme example, the higher-order function (f x)
is used to implement currying. It takes a single argument and returns a function. The evaluation of the expression ((f 3) 7)
first returns a function after evaluating (f 3)
. The returned function is (lambda (y) (+ 3 y))
. Then, it evaluates the returned function with 7 as the argument, returning 10. This is equivalent to the expression (add 3 7)
, since (f x)
is equivalent to the curried form of (add x y)
.
Erlang[edit]
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).
In this Erlang example, the higher-order function or_else
/2 takes a list of functions (Fs
) and argument (X
). It evaluates the function F
with the argument X
as argument. If the function F
returns false then the next function in Fs
will be evaluated. If the function F
returns {false,Y}
then the next function in Fs
with argument Y
will be evaluated. If the function F
returns R
the higher-order function or_else
/2 will return R
. Note that X
, Y
, and R
can be functions. The example returns false
.
Elixir[edit]
In Elixir, you can mix module definitions and anonymous functions
defmodule Hop do
def twice(f, v) do
f.(f.(v))
end
end
add3 = fn(v) -> 3 + v end
IO.puts Hop.twice(add3, 7) #13
Alternatively, we can also compose using pure anonymous functions.
twice = fn(f, v) -> f.(f.(v)) end
add3 = fn(v) -> 3 + v end
IO.puts twice.(add3, 7) #13
JavaScript[edit]
const twice = (f, v) => f(f(v));
const add3 = v => v + 3;
twice(add3, 7); // 13
Go[edit]
func twice(f func(int) int, v int) int {
return f(f(v))
}
func main() {
f := func(v int) int {
return v + 3
}
twice(f, 7) // returns 13
}
Notice a function literal can be defined either with an identifier (twice) or anonymously (assigned to variable f). Run full program on Go Playground!
Scala[edit]
def twice(f:Int=>Int) = f compose f
twice(_+3)(7) // 13
Java (1.8+)[edit]
Function<Function<Integer, Integer>, Function<Integer, Integer>> twice = f -> f.andThen(f);
twice.apply(x -> x + 3).apply(7); // 13
Kotlin[edit]
fun <T> twice(f: (T)->T): (T)->T = {f(f(it))}
fun f(x:Int) = x + 3
println(twice(::f)(7)) // 13
Lua[edit]
local twice = function(f,v)
return f(f(v))
end
local f = function(v)
return v + 3
end
print(twice(f,7)) -- 13
Swift[edit]
// generic function
func twice<T>(_ v: @escaping (T) -> T) -> (T) -> T {
return { v(v($0)) }
}
// inferred closure
let f = { $0 + 3 }
twice(f)(10) // 16
Rust[edit]
// Take function f(x), return function f(f(x))
fn twice<A>(function: impl Fn(A) -> A) -> impl Fn(A) -> A
{
move |a| function(function(a))
}
// Return x + 3
fn f(x: i32) -> i32 {
x + 3
}
fn main() {
let g = twice(f);
println!("{}", g(7));
}
Ruby[edit]
def twice(f, x)
f.call f.call(x)
end
add3 = ->(x) { x + 3 }
puts twice(add3, 7) #=> 13
C++[edit]
With generic lambdas provided by C++14:
#include <iostream>
auto twice = [](auto f, int v)
{
return f(f(v));
};
auto f = [](int i)
{
return i + 3;
};
int main()
{
std::cout << twice(f, 7) << std::endl;
}
Or, using std::function in C++11 :
#include <iostream>
#include <functional>
auto twice = [](const std::function<int(int)>& f, int v)
{
return f(f(v));
};
auto f = [](int i)
{
return i + 3;
};
int main()
{
std::cout << twice(f, 7) << std::endl;
}
D[edit]
import std.stdio : writeln;
alias twice = (f, i) => f(f(i));
alias f = (int i) => i + 3;
void main()
{
writeln(twice(f, 7));
}
ColdFusion Markup Language (CFML)[edit]
twice = function(f, v) {
return f(f(v));
};
f = function(v) {
return v + 3;
};
writeOutput(twice(f, 7)); // 13
PHP[edit]
$twice = function($f, $v) {
return $f($f($v));
};
$f = function($v) {
return $v + 3;
};
echo($twice($f, 7)); // 13
R[edit]
twice <- function(func) {
return(function(x) {
func(func(x))
})
}
f <- function(x) {
return(x + 3)
}
g <- twice(f)
> print(g(7))
[1] 13
Perl 6[edit]
sub twice(Callable:D $c) {
return sub { $c($c($^x)) };
}
sub f(Int:D $x) {
return $x + 3;
}
my $g = twice(&f);
say $g(7); #OUTPUT: 13
In Perl 6, all code objects are closures and therefore can reference inner "lexical" variables from an outer scope because the lexical variable is "closed" inside of the function. Perl 6 also supports "pointy block" syntax for lambda expressions which can be assigned to a variable or invoked anonymously.
Tcl[edit]
set twice {{f v} {apply $f [apply $f $v]}}
set f {{v} {return [expr $v + 3]}}
# result: 13
puts [apply $twice $f 7]
Tcl uses apply command to apply an anonymous function (since 8.6).
XQuery[edit]
declare function local:twice($f, $x) {
$f($f($x))
};
declare function local:f($x) {
$x + 3
};
local:twice(local:f#1, 7) (: 13 :)
XACML[edit]
The XACML standard defines higher-order functions in the standard to apply a function to multiple values of attribute bags.
rule allowEntry{
permit
condition anyOfAny(function[stringEqual], citizenships, allowedCitizenships)
}
The list of higher-order functions is can be found here.
Alternatives[edit]
Function pointers[edit]
Function pointers in languages such as C and C++ allow programmers to pass around references to functions. The following C code computes an approximation of the integral of an arbitrary function:
#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;
}
The qsort function from the C standard library uses a function pointer to emulate the behavior of a higher-order function.
Macros[edit]
Macros can also be used to achieve some of the effects of higher order functions. However, macros cannot easily avoid the problem of variable capture; they may also result in large amounts of duplicated code, which can be more difficult for a compiler to optimize. Macros are generally not strongly typed, although they may produce strongly typed code.
Dynamic code evaluation[edit]
In other imperative programming languages, it is possible to achieve some of the same algorithmic results as are obtained via higher-order functions by dynamically executing code (sometimes called Eval or Execute operations) in the scope of evaluation. There can be significant drawbacks to this approach:
- The argument code to be executed is usually not statically typed; these languages generally rely on dynamic typing to determine the well-formedness and safety of the code to be executed.
- The argument is usually provided as a string, the value of which may not be known until run-time. This string must either be compiled during program execution (using just-in-time compilation) or evaluated by interpretation, causing some added overhead at run-time, and usually generating less efficient code.
Objects[edit]
In object-oriented programming languages that do not support higher-order functions, objects can be an effective substitute. An object's methods act in essence like functions, and a method may accept objects as parameters and produce objects as return values. Objects often carry added run-time overhead compared to pure functions, however, and added boilerplate code for defining and instantiating an object and its method(s). Languages that permit stack-based (versus heap-based) objects or structs can provide more flexibility with this method.
An example of using a simple stack based record in Free Pascal with a function that returns a function:
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.
The function a()
takes a Txy
record as input and returns the integer value of the sum of the record's x
and y
fields (3 + 7).
Defunctionalization[edit]
Defunctionalization can be used to implement higher-order functions in languages that lack first-class functions:
// 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;
}
In this case, different types are used to trigger different functions via function overloading. The overloaded function in this example has the signature auto apply
.
See also[edit]
- First-class function
- Combinatory logic
- Function-level programming
- Functional programming
- Kappa calculus - a formalism for functions which excludes higher-order functions
- Strategy pattern
- Higher order messages