Higher-order function


In mathematics and computer science, a higher-order function is a function that does at least one of the following:
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.
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.

General examples

Direct support

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

Explicitly
let add3 x = x + 3
let twice f x = f
print_int
One-Line
print_int 7)

APL


twice←
plusthree←
g←

g 7
13

Or in a tacit manner:

twice←⍣2
plusthree←+∘3
g←plusthree twice

g 7
13

J

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

Python


>>> def twice:
... def result:
... return f
... return result
>>> plusthree = lambda x: x + 3
>>> g = twice

>>> g
13

Python decorator syntax is often used to replace a function with the result of passing that function through a higher-order function. E.g., the function could be implemented equivalently:

>>> @twice
... def g:
... return x + 3
>>> g
13

Wolfram Language


In:= Nest
Out:= 13

Pascal


type fun = function: Integer;
function add3: Integer;
begin
result := x + 3;
end;
function twice: Integer;
begin
result := func;
end;
begin
writeln;
end.

F#


let twice f = f >> f
let f = 3
twice f 7 |> printf "%A" // 13

D


int delegate twice
import std.stdio;
int plusThree
writeln); // 13

C#


Func, Func> twice = f => x => f;
Func plusThree = x => x + 3;
Console.WriteLine); // 13

Haskell


twice :: ->
twice f = f. f
f :: Num a => a -> a
f = subtract 3
main :: IO
main = print -- 1

Or more quickly:

twice f = f. f
main = print $ twice 7 -- 13

Clojure


;13

In Clojure, "#" starts a lambda expression, and "%" refers to the next function argument.

Scheme


)
))
)

In this Scheme example, the higher-order function is used to implement currying. It takes a single argument and returns a function. The evaluation of the expression first returns a function after evaluating . The returned function is ). Then, it evaluates the returned function with 7 as the argument, returning 10. This is equivalent to the expression , since is equivalent to the curried form of .

Erlang


or_else -> false;
or_else -> or_else.
or_else -> or_else;
or_else -> or_else;
or_else -> R.
or_else.

In this Erlang example, the higher-order function or_else/2 takes a list of functions and argument. 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 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

In Elixir, you can mix module definitions and anonymous functions

defmodule Hop do
def twice do
f.
end
end
add3 = fn -> 3 + v end
IO.puts Hop.twice #13

Alternatively, we can also compose using pure anonymous functions.

twice = fn -> f. end
add3 = fn -> 3 + v end
IO.puts twice. #13

JavaScript


const twice = => f;
const add3 = v => v + 3;
twice; // 13

Go


func twice int
func main

Notice a function literal can be defined either with an identifier or anonymously. Run full program on .

Scala


def twice = f compose f
twice // 13

Java (1.8+)


Function twice = f -> f.andThen;
twice.apply.applyAsInt; // 13

Julia


julia> function twice
function result
return f
end
return result
end
twice
julia> plusthree = x + 3
plusthree
julia> g = twice

julia> g
13

Kotlin


fun twice: ->T =
fun f = x + 3
println) // 13

Lua


local twice = function
return f
end
local addthree = function
return v + 3
end
print -- 13

MATLAB


function result = twice
result = fnhandle;
end
addthree = @ n + 3;
disp; % 13

Swift


// generic function
func twice -> -> T
// inferred closure
let f =
twice // 16

Rust


// Take function f, return function f
fn twice -> impl Fn -> A
// Return x + 3
fn plusthree -> i32
fn main

Ruby


def twice
f.call f.call
end
add3 = ->
puts twice #=> 13

C

With function pointers in C:

  1. include
typedef int ;
int add3
int twice
int main


C++

With generic lambdas provided by C++14:

  1. include
auto twice =

auto f =
int main

Or, using std::function in C++11 :

  1. include
  2. include
auto twice =

auto f =

int main

D


import std.stdio : writeln;
alias twice = => f;
alias f = => i + 3;
void main

ColdFusion Markup Language (CFML)


twice = function ;
f = function ;
writeOutput; // 13

PHP


$twice = function ;
$f = function ;
echo; // 13

R


twice <- function
f <- function
g <- twice
> print
13

Perl


sub add3
sub twice
say twice->; # 13

or with all functions in variables:

my $add3 = sub ;
my $twice = sub ;
my $g = $twice->;
say $g->; # 13

Raku


sub twice
sub f
my $g = twice;
say $g; #OUTPUT: 13

In Raku, 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


set twice
set f
  1. result: 13
puts

Tcl uses apply command to apply an anonymous function.

XQuery


declare function local:twice ;
declare function local:f ;
local:twice

XACML

The XACML standard defines higher-order functions in the standard to apply a function to multiple values of attribute bags.

rule allowEntry

The list of higher-order functions in XACML can be found here.

Alternatives

Function pointers

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

  1. include
double square
double cube
/* Compute the integral of f within the interval */
double integral
int main

The qsort function from the C standard library uses a function pointer to emulate the behavior of a higher-order function.

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

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 in the scope of evaluation. There can be significant drawbacks to this approach:
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. Languages that permit stack-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 : int;

function f: int;
begin
Result := xy.y + xy.x;
end;
function g: Tf;
begin
result := func;
end;
var
a: Tf;
xy: Txy = ;
begin
a := g; // return a function to "a"
writeln; // 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.

Defunctionalization

can be used to implement higher-order functions in languages that lack first-class functions:

// Defunctionalized function data structures
template struct Add ;
template struct DivBy ;
template struct Composition ;
// Defunctionalized function application implementations
template
auto apply
template
auto apply
template
auto apply
// Higher-order compose function
template
Composition compose
int main

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.