Higher-order function

Last updated February 10, 2024

In mathematics and computer science, a higher-order function (HOF) 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 (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 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.

APL

twice←{⍺⍺⍺⍺⍵}plusthree←{⍵+3}g←{plusthreetwice⍵}g713

Or in a tacit manner:

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

C++

Using std::function in C++11:

#include<iostream>#include<functional>autotwice=[](conststd::function<int(int)>&f){return[f](intx){returnf(f(x));};};autoplus_three=[](inti){returni+3;};intmain(){autog=twice(plus_three);std::cout<<g(7)<<'\n';// 13}

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

#include<iostream>autotwice=[](constauto&f){return[f](intx){returnf(f(x));};};autoplus_three=[](inti){returni+3;};intmain(){autog=twice(plus_three);std::cout<<g(7)<<'\n';// 13}

C#

Using just delegates:

usingSystem;publicclassProgram{publicstaticvoidMain(string[]args){Func<Func<int,int>,Func<int,int>>twice=f=>x=>f(f(x));Func<int,int>plusThree=i=>i+3;varg=twice(plusThree);Console.WriteLine(g(7));// 13}}

Or equivalently, with static methods:

usingSystem;publicclassProgram{privatestaticFunc<int,int>Twice(Func<int,int>f){returnx=>f(f(x));}privatestaticintPlusThree(inti)=>i+3;publicstaticvoidMain(string[]args){varg=Twice(PlusThree);Console.WriteLine(g(7));// 13}}

Clojure

(defn twice[f](fn [x](f(fx))))(defn plus-three[i](+ i3))(def g(twiceplus-three))(println (g7)); 13

ColdFusion Markup Language (CFML)

twice=function(f){returnfunction(x){returnf(f(x));};};plusThree=function(i){returni+3;};g=twice(plusThree);writeOutput(g(7));// 13

Common Lisp

(defuntwice(f)(lambda(x)(funcallf(funcallfx))))(defunplus-three(i)(+i3))(defvarg(twice#'plus-three))(print(funcallg7))

D

importstd.stdio:writeln;aliastwice=(f)=>(intx)=>f(f(x));aliasplusThree=(inti)=>i+3;voidmain(){autog=twice(plusThree);writeln(g(7));// 13}

Dart

intFunction(int)twice(intFunction(int)f){return(x){returnf(f(x));};}intplusThree(inti){returni+3;}voidmain(){finalg=twice(plusThree);print(g(7));// 13}

Elixir

In Elixir, you can mix module definitions and anonymous functions

defmoduleHofdodeftwice(f)dofn(x)->f.(f.(x))endendendplus_three=fn(i)->i+3endg=Hof.twice(plus_three)IO.putsg.(7)# 13

Alternatively, we can also compose using pure anonymous functions.

twice=fn(f)->fn(x)->f.(f.(x))endendplus_three=fn(i)->i+3endg=twice.(plus_three)IO.putsg.(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([funerlang:is_integer/1,funerlang:is_atom/1,funerlang: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.

F#

lettwicef=f>>fletplus_three=(+)3letg=twiceplus_threeg7|>printf"%A"// 13

Go

packagemainimport"fmt"functwice(ffunc(int)int)func(int)int{returnfunc(xint)int{returnf(f(x))}}funcmain(){plusThree:=func(iint)int{returni+3}g:=twice(plusThree)fmt.Println(g(7))// 13}

Notice a function literal can be defined either with an identifier (twice) or anonymously (assigned to variable plusThree).

Haskell

twice::(Int->Int)->(Int->Int)twicef=f.fplusThree::Int->IntplusThree=(+3)main::IO()main=print(g7)-- 13whereg=twiceplusThree

J

Explicitly,

twice=.adverb:'u u y'plusthree=.verb:'y + 3'g=.plusthreetwiceg713

or tacitly,

twice=.^:2plusthree=.+&3g=.plusthreetwiceg713

Java (1.8+)

Using just functional interfaces:

importjava.util.function.*;classMain{publicstaticvoidmain(String[]args){Function<IntUnaryOperator,IntUnaryOperator>twice=f->f.andThen(f);IntUnaryOperatorplusThree=i->i+3;varg=twice.apply(plusThree);System.out.println(g.applyAsInt(7));// 13}}

Or equivalently, with static methods:

importjava.util.function.*;classMain{privatestaticIntUnaryOperatortwice(IntUnaryOperatorf){returnf.andThen(f);}privatestaticintplusThree(inti){returni+3;}publicstaticvoidmain(String[]args){varg=twice(Main::plusThree);System.out.println(g.applyAsInt(7));// 13}}

JavaScript

With arrow functions:

"use strict";consttwice=f=>x=>f(f(x));constplusThree=i=>i+3;constg=twice(plusThree);console.log(g(7));// 13

Or with classical syntax:

"use strict";functiontwice(f){returnfunction(x){returnf(f(x));};}functionplusThree(i){returni+3;}constg=twice(plusThree);console.log(g(7));// 13

Julia

julia>functiontwice(f)functionresult(x)returnf(f(x))endreturnresultendtwice (generic function with 1 method)julia>plusthree(i)=i+3plusthree (generic function with 1 method)julia>g=twice(plusthree)(::var"#result#3"{typeof(plusthree)}) (generic function with 1 method)julia>g(7)13

Kotlin

funtwice(f:(Int)->Int):(Int)->Int{return{f(f(it))}}funplusThree(i:Int)=i+3funmain(){valg=twice(::plusThree)println(g(7))// 13}

Lua

functiontwice(f)returnfunction(x)returnf(f(x))endendfunctionplusThree(i)returni+3endlocalg=twice(plusThree)print(g(7))-- 13

MATLAB

functionresult=twice(f)result=@(x)f(f(x));endplusthree=@(i)i+3;g=twice(plusthree)disp(g(7));% 13

OCaml

lettwicefx=f(fx)letplus_three=(+)3let()=letg=twiceplus_threeinprint_int(g7);(* 13 *)print_newline()

PHP

<?phpdeclare(strict_types=1);functiontwice(callable$f):Closure{returnfunction(int$x)use($f):int{return$f($f($x));};}functionplusThree(int$i):int{return$i+3;}$g=twice('plusThree');echo$g(7),"\n";// 13

or with all functions in variables:

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

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

Perl

usestrict;usewarnings;subtwice{my($f)=@_;sub{$f->($f->(@_));};}subplusThree{my($i)=@_;$i+3;}my$g=twice(\&plusThree);print$g->(7),"\n";# 13

or with all functions in variables:

usestrict;usewarnings;my$twice=sub{my($f)=@_;sub{$f->($f->(@_));};};my$plusThree=sub{my($i)=@_;$i+3;};my$g=$twice->($plusThree);print$g->(7),"\n";# 13

Python

>>> deftwice(f):... defresult(x):... returnf(f(x))... returnresult>>> plus_three=lambdai:i+3>>> g=twice(plus_three)>>> g(7)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 g could be implemented equivalently:

>>> @twice... defg(i):... returni+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

subtwice(Callable:D$f) {     returnsub { $f($f($^x)) }; }  subplusThree(Int:D$i) {     return$i + 3; }  my$g = twice(&plusThree);  say$g(7); # 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

deftwice(f)->(x){f.call(f.call(x))}endplus_three=->(i){i+3}g=twice(plus_three)putsg.call(7)# 13

Rust

fntwice(f: implFn(i32)-> i32)-> implFn(i32)-> i32{move|x|f(f(x))}fnplus_three(i: i32)-> i32{i+3}fnmain(){letg=twice(plus_three);println!("{}",g(7))// 13}

Scala

objectMain{deftwice(f:Int=>Int):Int=>Int=fcomposefdefplusThree(i:Int):Int=i+3defmain(args:Array[String]):Unit={valg=twice(plusThree)print(g(7))// 13}}

Scheme

(define(twicef)(lambda(x)(f(fx))))(define(plus-threei)(+i3))(defineg(twiceplus-three))(display(g7)); 13(display"\n")

Swift

functwice(_f:@escaping(Int)->Int)->(Int)->Int{return{f(f($0))}}letplusThree={$0+3}letg=twice(plusThree)print(g(7))// 13

Tcl

settwice{{fx}{apply$f[apply$f$x]}}setplusThree{{i}{return[expr$i+3]}}# result: 13puts[apply$twice$plusThree7]

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.

ruleallowEntry{permitconditionanyOfAny(function[stringEqual],citizenships,allowedCitizenships)}

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

XQuery

declarefunctionlocal:twice($f,$x){$f($f($x))};declarefunctionlocal:plusthree($i){$i+3};local:twice(local:plusthree#1,7)(: 13 :)

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>doublesquare(doublex){returnx*x;}doublecube(doublex){returnx*x*x;}/* Compute the integral of f() within the interval [a,b] */doubleintegral(doublef(doublex),doublea,doubleb,intn){inti;doublesum=0;doubledt=(b-a)/n;for(i=0;i<n;++i){sum+=f(a+(i+0.5)*dt);}returnsum*dt;}intmain(){printf("%g\n",integral(square,0,1,100));printf("%g\n",integral(cube,0,1,100));return0;}

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:

programexample;typeint=integer;Txy=recordx,y:int;end;Tf=function(xy:Txy):int;functionf(xy:Txy):int;beginResult:=xy.y+xy.x;end;functiong(func:Tf):Tf;beginresult:=func;end;vara:Tf;xy:Txy=(x:3;y:7);begina:=g(@f);// return a function to "a"writeln(a(xy));// prints 10end.

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:

// Defunctionalized function data structurestemplate<typenameT>structAdd{Tvalue;};template<typenameT>structDivBy{Tvalue;};template<typenameF,typenameG>structComposition{Ff;Gg;};// Defunctionalized function application implementationstemplate<typenameF,typenameG,typenameX>autoapply(Composition<F,G>f,Xarg){returnapply(f.f,apply(f.g,arg));}template<typenameT,typenameX>autoapply(Add<T>f,Xarg){returnarg+f.value;}template<typenameT,typenameX>autoapply(DivBy<T>f,Xarg){returnarg/f.value;}// Higher-order compose functiontemplate<typenameF,typenameG>Composition<F,G>compose(Ff,Gg){returnComposition<F,G>{f,g};}intmain(intargc,constchar*argv[]){autof=compose(DivBy<float>{2.0f},Add<int>{5});apply(f,3);// 4.0fapply(f,9);// 7.0freturn0;}

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.

Related Research Articles

A quine is a computer program which takes no input and produces a copy of its own source code as its only output. The standard terms for these programs in the computability theory and computer science literature are "self-replicating programs", "self-reproducing programs", and "self-copying programs".

In programming languages, a closure, also lexical closure or function closure, is a technique for implementing lexically scoped name binding in a language with first-class functions. Operationally, a closure is a record storing a function together with an environment. The environment is a mapping associating each free variable of the function with the value or reference to which the name was bound when the closure was created. Unlike a plain function, a closure allows the function to access those captured variables through the closure's copies of their values or references, even when the function is invoked outside their scope.

In computer programming, lazy initialization is the tactic of delaying the creation of an object, the calculation of a value, or some other expensive process until the first time it is needed. It is a kind of lazy evaluation that refers specifically to the instantiation of objects or other resources.

Template metaprogramming (TMP) is a metaprogramming technique in which templates are used by a compiler to generate temporary source code, which is merged by the compiler with the rest of the source code and then compiled. The output of these templates can include compile-time constants, data structures, and complete functions. The use of templates can be thought of as compile-time polymorphism. The technique is used by a number of languages, the best-known being C++, but also Curl, D, Nim, and XL.

In programming language theory and type theory, polymorphism is the use of a single symbol to represent multiple different types.

In computer science, a type signature or type annotation defines the inputs and outputs of a function, subroutine or method. A type signature includes the number, types, and order of the function's arguments. One important use of a type signature is for function overload resolution, where one particular definition of a function to be called is selected among many overloaded forms.

A function pointer, also called a subroutine pointer or procedure pointer, is a pointer referencing executable code, rather than data. Dereferencing the function pointer yields the referenced function, which can be invoked and passed arguments just as in a normal function call. Such an invocation is also known as an "indirect" call, because the function is being invoked indirectly through a variable instead of directly through a fixed identifier or address.

In computer programming, a callback or callback function is any reference to executable code that is passed as an argument to another piece of code; that code is expected to call back (execute) the callback function as part of its job. This execution may be immediate as in a synchronous callback, or it might happen at a later point in time as in an asynchronous callback. They are also called blocking and non-blocking.

In mathematics and in computer programming, a variadic function is a function of indefinite arity, i.e., one which accepts a variable number of arguments. Support for variadic functions differs widely among programming languages.

In computer science, function composition is an act or mechanism to combine simple functions to build more complicated ones. Like the usual composition of functions in mathematics, the result of each function is passed as the argument of the next, and the result of the last one is the result of the whole.

The curiously recurring template pattern (CRTP) is an idiom, originally in C++, in which a class X derives from a class template instantiation using X itself as a template argument. More generally it is known as F-bound polymorphism, and it is a form of F-bounded quantification.

C++11 is a version of the ISO/IEC 14882 standard for the C++ programming language. C++11 replaced the prior version of the C++ standard, called C++03, and was later replaced by C++14. The name follows the tradition of naming language versions by the publication year of the specification, though it was formerly named C++0x because it was expected to be published before 2010.

In computer programming, an anonymous function is a function definition that is not bound to an identifier. Anonymous functions are often arguments being passed to higher-order functions or used for constructing the result of a higher-order function that needs to return a function. If the function is only used once, or a limited number of times, an anonymous function may be syntactically lighter than using a named function. Anonymous functions are ubiquitous in functional programming languages and other languages with first-class functions, where they fulfil the same role for the function type as literals do for other data types.

In mathematics and computer science, apply is a function that applies a function to arguments. It is central to programming languages derived from lambda calculus, such as LISP and Scheme, and also in functional languages. It has a role in the study of the denotational semantics of computer programs, because it is a continuous function on complete partial orders. Apply is also a continuous function in homotopy theory, and, indeed underpins the entire theory: it allows a homotopy deformation to be viewed as a continuous path in the space of functions. Likewise, valid mutations (refactorings) of computer programs can be seen as those that are "continuous" in the Scott topology.

The syntax and semantics of PHP, a programming language, form a set of rules that define how a PHP program can be written and interpreted.

In computer programming, variable shadowing occurs when a variable declared within a certain scope has the same name as a variable declared in an outer scope. At the level of identifiers, this is known as name masking. This outer variable is said to be shadowed by the inner variable, while the inner identifier is said to mask the outer identifier. This can lead to confusion, as it may be unclear which variable subsequent uses of the shadowed variable name refer to, which depends on the name resolution rules of the language.

In computer programming, variadic templates are templates that take a variable number of arguments.

In programming languages and type theory, an option type or maybe type is a polymorphic type that represents encapsulation of an optional value; e.g., it is used as the return type of functions which may or may not return a meaningful value when they are applied. It consists of a constructor which either is empty, or which encapsulates the original data type A.

In computer science, partial application refers to the process of fixing a number of arguments of a function, producing another function of smaller arity. Given a function $, we might fix the first argument, producing a function of type . Evaluation of this function might be represented as . Note that the result of partial function application in this case is a function that takes two arguments. Partial application is sometimes incorrectly called currying, which is a related, but distinct concept.$

Different command-line argument parsing methods are used by different programming languages to parse command-line arguments.

References

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

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

[1]