Higher-order function

In mathematics and computer science, a higher-order function (HOF) is a function that does at least one of the following:

takes one or more functions as arguments (i.e. a procedural parameter, which is a parameter of a procedure that is itself a procedure),
returns a function or value 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 $(\tau _{1}\to \tau _{2})\to \tau _{3}$ .

General examples

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 collection of elements, and as the result, returns a new collection with f applied to each element from the collection.
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.
filter
fold
apply
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 <syntaxhighlight lang="text" class="" style="" inline="1">twice</syntaxhighlight> takes a function, and applies the function to some value twice. If <syntaxhighlight lang="text" class="" style="" inline="1">twice</syntaxhighlight> has to be applied several times for the same <syntaxhighlight lang="text" class="" style="" inline="1">f</syntaxhighlight> it preferably should return a function rather than a value. This is in line with the "don't repeat yourself" principle.

APL

     twice←{⍺⍺ ⍺⍺ ⍵}

     plusthree←{⍵+3}

     g←{plusthree twice ⍵}
   
     g 7

13 </syntaxhighlight>

Or in a tacit manner:

     twice←⍣2

     plusthree←+∘3

     g←plusthree twice
   
     g 7

13 </syntaxhighlight>

C++

Using <syntaxhighlight lang="text" class="" style="" inline="1">std::function</syntaxhighlight> in 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

} </syntaxhighlight>

Or, with generic lambdas provided by 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

} </syntaxhighlight>

C#

Using just delegates:

<syntaxhighlight lang="csharp"> 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
   }

} </syntaxhighlight>

Or equivalently, with static methods:

<syntaxhighlight lang="csharp"> 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
   }

} </syntaxhighlight>

Clojure

<syntaxhighlight lang="clojure"> (defn twice [f]

 (fn [x] (f (f x))))

(defn plus-three [i]

 (+ i 3))

(def g (twice plus-three))

(println (g 7)) ; 13 </syntaxhighlight>

ColdFusion Markup Language (CFML)

<syntaxhighlight lang="cfs"> twice = function(f) {

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

};

plusThree = function(i) {

   return i + 3;

};

g = twice(plusThree);

writeOutput(g(7)); // 13 </syntaxhighlight>

Common Lisp

<syntaxhighlight lang="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)) </syntaxhighlight>

D

<syntaxhighlight lang="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

} </syntaxhighlight>

Dart

<syntaxhighlight lang="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

} </syntaxhighlight>

Elixir

In Elixir, you can mix module definitions and anonymous functions

<syntaxhighlight lang="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 </syntaxhighlight>

Alternatively, we can also compose using pure anonymous functions.

<syntaxhighlight lang="elixir"> 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 </syntaxhighlight>

Erlang

<syntaxhighlight lang="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). </syntaxhighlight>

In this Erlang example, the higher-order function <syntaxhighlight lang="text" class="" style="" inline="1">or_else/2</syntaxhighlight> takes a list of functions (<syntaxhighlight lang="text" class="" style="" inline="1">Fs</syntaxhighlight>) and argument (<syntaxhighlight lang="text" class="" style="" inline="1">X</syntaxhighlight>). It evaluates the function <syntaxhighlight lang="text" class="" style="" inline="1">F</syntaxhighlight> with the argument <syntaxhighlight lang="text" class="" style="" inline="1">X</syntaxhighlight> as argument. If the function <syntaxhighlight lang="text" class="" style="" inline="1">F</syntaxhighlight> returns false then the next function in <syntaxhighlight lang="text" class="" style="" inline="1">Fs</syntaxhighlight> will be evaluated. If the function <syntaxhighlight lang="text" class="" style="" inline="1">F</syntaxhighlight> returns <syntaxhighlight lang="text" class="" style="" inline="1">{false, Y} </syntaxhighlight> then the next function in <syntaxhighlight lang="text" class="" style="" inline="1">Fs</syntaxhighlight> with argument <syntaxhighlight lang="text" class="" style="" inline="1">Y</syntaxhighlight> will be evaluated. If the function <syntaxhighlight lang="text" class="" style="" inline="1">F</syntaxhighlight> returns <syntaxhighlight lang="text" class="" style="" inline="1">R</syntaxhighlight> the higher-order function <syntaxhighlight lang="text" class="" style="" inline="1">or_else/2</syntaxhighlight> will return <syntaxhighlight lang="text" class="" style="" inline="1">R</syntaxhighlight>. Note that <syntaxhighlight lang="text" class="" style="" inline="1">X</syntaxhighlight>, <syntaxhighlight lang="text" class="" style="" inline="1">Y</syntaxhighlight>, and <syntaxhighlight lang="text" class="" style="" inline="1">R</syntaxhighlight> can be functions. The example returns <syntaxhighlight lang="text" class="" style="" inline="1">false</syntaxhighlight>.

F#

<syntaxhighlight lang="fsharp"> let twice f = f >> f

let plus_three = (+) 3

let g = twice plus_three

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

Go

<syntaxhighlight lang="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 } </syntaxhighlight>

Notice a function literal can be defined either with an identifier (<syntaxhighlight lang="text" class="" style="" inline="1">twice</syntaxhighlight>) or anonymously (assigned to variable <syntaxhighlight lang="text" class="" style="" inline="1">plusThree</syntaxhighlight>).

Haskell

<syntaxhighlight lang="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

</syntaxhighlight>

J

Explicitly,

  twice=.     adverb : 'u u y'

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

13 </syntaxhighlight>

or tacitly,

  twice=. ^:2

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

13 </syntaxhighlight>

Java (1.8+)

Using just functional interfaces:

<syntaxhighlight lang="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
   }

} </syntaxhighlight>

Or equivalently, with static methods:

<syntaxhighlight lang="java"> 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
   }

} </syntaxhighlight>

JavaScript

With arrow functions:

<syntaxhighlight lang="javascript"> "use strict";

const twice = f => x => f(f(x));

const plusThree = i => i + 3;

const g = twice(plusThree);

console.log(g(7)); // 13 </syntaxhighlight>

Or with classical syntax:

<syntaxhighlight lang="javascript"> "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 </syntaxhighlight>

Julia

<syntaxhighlight lang="jlcon"> 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 </syntaxhighlight>

Kotlin

<syntaxhighlight lang="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

} </syntaxhighlight>

Lua

<syntaxhighlight lang="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 </syntaxhighlight>

MATLAB

<syntaxhighlight lang="matlab"> function result = twice(f) result = @(x) f(f(x)); end

plusthree = @(i) i + 3;

g = twice(plusthree)

disp(g(7)); % 13 </syntaxhighlight>

OCaml

<syntaxhighlight lang="ocaml" start="1"> 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 ()

</syntaxhighlight>

PHP

<syntaxhighlight lang="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 </syntaxhighlight>

or with all functions in variables:

<syntaxhighlight lang="php"> <?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 </syntaxhighlight>

Note that arrow functions implicitly capture any variables that come from the parent scope,^[1] whereas anonymous functions require the <syntaxhighlight lang="text" class="" style="" inline="1">use</syntaxhighlight> keyword to do the same.

Perl

<syntaxhighlight lang="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 </syntaxhighlight>

or with all functions in variables:

<syntaxhighlight lang="perl"> 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 </syntaxhighlight>

Python

<syntaxhighlight lang="pycon"> >>> 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 </syntaxhighlight>

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 <syntaxhighlight lang="text" class="" style="" inline="1">g</syntaxhighlight> could be implemented equivalently:

<syntaxhighlight lang="pycon"> >>> @twice ... def g(i): ... return i + 3

>>> g(7) 13 </syntaxhighlight>

R

<syntaxhighlight lang="R"> twice <- \(f) \(x) f(f(x))

plusThree <- function(i) i + 3

g <- twice(plusThree)

> g(7) [1] 13 </syntaxhighlight>

Raku

<syntaxhighlight lang="perl6"> 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 </syntaxhighlight>

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

<syntaxhighlight lang="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 </syntaxhighlight>

Rust

<syntaxhighlight lang="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

} </syntaxhighlight>

Scala

<syntaxhighlight lang="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
 }

} </syntaxhighlight>

Scheme

<syntaxhighlight lang="scheme"> (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") </syntaxhighlight>

Swift

<syntaxhighlight lang="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 </syntaxhighlight>

Tcl

<syntaxhighlight lang="tcl"> set twice {{f x} {apply $f [apply $f $x]}} set plusThree {{i} {return [expr $i + 3]}}

result: 13

puts [apply $twice $plusThree 7] </syntaxhighlight>

Tcl uses apply command to apply an anonymous function (since 8.6).

XACML

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

<syntaxhighlight lang="xquery"> rule allowEntry{

   permit
   condition anyOfAny(function[stringEqual], citizenships, allowedCitizenships)

} </syntaxhighlight>

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

XQuery

<syntaxhighlight lang="xquery"> declare function local:twice($f, $x) {

 $f($f($x))

};

declare function local:plusthree($i) {

 $i + 3

};

local:twice(local:plusthree#1, 7) (: 13 :) </syntaxhighlight>

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

} </syntaxhighlight>

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

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:

<syntaxhighlight lang="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. </syntaxhighlight>

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

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

<syntaxhighlight lang="cpp"> // 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;

} </syntaxhighlight>

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.

References

^ "PHP: Arrow Functions - Manual". www.php.net. Retrieved 2021-03-01.

[1] "PHP: Arrow Functions - Manual". www.php.net. Retrieved 2021-03-01.

[1]

Higher-order function

General examples

Support in programming languages

Direct support

APL

C++

C#

Clojure

ColdFusion Markup Language (CFML)

Common Lisp

D

Dart

Elixir

Erlang

F#

Go

Haskell

J

Java (1.8+)

JavaScript

Julia

Kotlin

Lua

MATLAB

OCaml

PHP

Perl

Python

R

Raku

Ruby

Rust

Scala

Scheme

Swift

Tcl

XACML

XQuery

Alternatives

Function pointers

Macros

Dynamic code evaluation

Objects

Defunctionalization

See also

References