Higher-order function

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

General examples

function, found in many functional programming languages, is one example of a higher-order function. It takes arguments as a function f and a collection of elements, and as the result, returns a new collection with f applied to each element from the collection.
, 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.
Function composition
Integration
Callback
Tree traversal
Montague grammar, a semantic theory of natural language, uses higher-order functions

Support in programming languages

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 takes a function, and applies the function to some value twice. If has to be applied several times for the same it preferably should return a function rather than a value. This is in line with the "don't repeat yourself" principle.

APL

twice←
plusthree←
g←

g 7
13

Or in a tacit manner:

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

g 7
13

C++

Using in C++11:

import std;
auto twice = -> auto ;
auto plusThree = -> int ;
int main

Or, with generic lambdas provided by C++14:

import std;
auto twice = -> auto ;
auto plusThree = -> int ;
int main

C#

Using just delegates:

using System;
public class Program

Or equivalently, with static methods:

using System;
public class Program

Clojure

)
; 13

ColdFusion Markup Language (CFML)

twice = function ;
plusThree = function ;
g = twice;
writeOutput; // 13

Common Lisp

)

)

D

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

Dart

int Function twice
int plusThree
void main

Elixir

In Elixir, you can mix module definitions and anonymous functions

defmodule Hof do
def twice do
fn -> f. end
end
end
plus_three = fn -> i + 3 end
g = Hof.twice
IO.puts g. # 13

Alternatively, we can also compose using pure anonymous functions.

twice = fn ->
fn -> f. end
end
plus_three = fn -> i + 3 end
g = twice.
IO.puts g. # 13

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 takes a list of functions and argument. It evaluates the function with the argument as argument. If the function returns false then the next function in will be evaluated. If the function returns then the next function in with argument will be evaluated. If the function returns the higher-order function will return. Note that,, and can be functions. The example returns.

F#

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 func int
func main

Notice a function literal can be defined either with an identifier or anonymously.

Groovy

def twice =
def plusThree =
def g = twice.curry
println g // 13

Haskell

twice :: ->
twice f = f. f
plusThree :: Int -> Int
plusThree =
main :: IO
main = print -- 13
where
g = twice plusThree

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

Java (1.8+)

Using just functional interfaces:

import java.util.function.*;
class Main

Or equivalently, with static methods:

import java.util.function.*;
class Main

JavaScript

With arrow functions:

"use strict";
const twice = f => x => f;
const plusThree = i => i + 3;
const g = twice;
console.log; // 13

Or with classical syntax:

"use strict";
function twice
function plusThree
const g = twice;
console.log; // 13

Julia

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

julia> g
13

Kotlin

fun twice: -> Int
fun plusThree = i + 3
fun main

Lua

function twice
return function
return f
end
end
function plusThree
return i + 3
end
local g = twice
print -- 13

MATLAB

function result = twice
result = @ f;
end
plusthree = @ i + 3;
g = twice
disp; % 13

OCaml

let twice f x =
f
let plus_three =
3
let =
let g = twice plus_three in
print_int ;
print_newline

PHP

declare;
function twice: Closure
function plusThree: int
$g = twice;
echo $g, "\n"; // 13

or with all functions in variables:

declare;
$twice = fn: Closure => fn: int => $f;
$plusThree = fn: int => $i + 3;
$g = $twice;
echo $g, "\n"; // 13

Note that arrow functions implicitly capture any variables that come from the parent scope, whereas anonymous functions require the keyword to do the same.

Perl

use strict;
use warnings;
sub twice
sub plusThree
my $g = twice;
print $g->, "\n"; # 13

or with all functions in variables:

use strict;
use warnings;
my $twice = sub ;
my $plusThree = sub ;
my $g = $twice->;
print $g->, "\n"; # 13

Python

def twice -> Any:
def result -> Any:
return f
return result
plus_three: Callable = lambda i: i + 3
g: int = twice

print

prints 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 -> int:
return i + 3
print

prints 13

R

twice <- \ \ f
plusThree <- function i + 3
g <- twice
> g
13

Raku

sub twice
sub plusThree
my $g = twice;
say $g; # 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. Raku also supports "pointy block" syntax for lambda expressions which can be assigned to a variable or invoked anonymously.

Ruby

def twice
->
end
plus_three = ->
g = twice
puts g.call # 13

Rust

fn twice -> impl Fn -> i32
fn plus_three -> i32
fn main

Scala

object Main

Scheme

)

)
)
; 13

Swift

func twice -> -> Int
let plusThree =
let g = twice
print // 13

Tcl

set twice
set plusThree

result: 13

puts

Tcl uses apply command to apply an anonymous function.

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.

XQuery

declare function local:twice ;
declare function local:plusthree ;
local:twice

Alternatives

Function pointers

Function pointers in languages such as C, C++, Fortran, and Pascal allow programmers to pass around references to functions. The following C code computes an approximation of the integral of an arbitrary function:

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

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:

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 or evaluated by interpretation, causing some added overhead at run-time, and usually generating less efficient code.

Objects

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

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.