 | This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Higher-order function" – news ·newspapers ·books ·scholar ·JSTOR(November 2024) (Learn how and when to remove this message) |
Inmathematics andcomputer science, ahigher-order function (HOF) is afunction that does at least one of the following:
All other functions arefirst-order functions. In mathematics higher-order functions are also termedoperators orfunctionals. Thedifferential operator incalculus is a common example, since it maps a function to itsderivative, also a function. Higher-order functions should not be confused with other uses of the word "functor" throughout mathematics, seeFunctor (disambiguation).
In the untypedlambda calculus, all functions are higher-order; in atyped lambda calculus, from which mostfunctional programming languages are derived, higher-order functions that take one function as argument are values with types of the form.
map function, found in many functional programming languages, is one example of a higher-order function. It takes arguments as a functionf and a collection of elements, and as the result, returns a new collection withf applied to each element from the collection.qsort is an example of this.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 functiontwice takes a function, and applies the function to some value twice. Iftwice has to be applied several times for the samef it preferably should return a function rather than a value. This is in line with the "don't repeat yourself" principle.
twice←{⍺⍺⍺⍺⍵}plusthree←{⍵+3}g←{plusthreetwice⍵}g713
Or in a tacit manner:
twice←⍣2plusthree←+∘3g←plusthreetwiceg713
Usingstd::function inC++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}
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}}
(defntwice[f](fn[x](f(fx))))(defnplus-three[i](+i3))(defg(twiceplus-three))(println(g7)); 13
twice=function(f){returnfunction(x){returnf(f(x));};};plusThree=function(i){returni+3;};g=twice(plusThree);writeOutput(g(7));// 13
(defuntwice(f)(lambda(x)(funcallf(funcallfx))))(defunplus-three(i)(+i3))(defvarg(twice#'plus-three))(print(funcallg7))
importstd.stdio:writeln;aliastwice=(f)=>(intx)=>f(f(x));aliasplusThree=(inti)=>i+3;voidmain(){autog=twice(plusThree);writeln(g(7));// 13}
intFunction(int)twice(intFunction(int)f){return(x){returnf(f(x));};}intplusThree(inti){returni+3;}voidmain(){finalg=twice(plusThree);print(g(7));// 13}
In Elixir, you can mix module definitions andanonymous 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
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 functionor_else/2 takes a list of functions (Fs) and argument (X). It evaluates the functionF with the argumentX as argument. If the functionF returns false then the next function inFs will be evaluated. If the functionF returns{false, Y} then the next function inFs with argumentY will be evaluated. If the functionF returnsR the higher-order functionor_else/2 will returnR. Note thatX,Y, andR can be functions. The example returnsfalse.
lettwicef=f>>fletplus_three=(+)3letg=twiceplus_threeg7|>printf"%A"// 13
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 variableplusThree).
deftwice={f,x->f(f(x))}defplusThree={it+3}defg=twice.curry(plusThree)printlng(7)// 13
twice::(Int->Int)->(Int->Int)twicef=f.fplusThree::Int->IntplusThree=(+3)main::IO()main=print(g7)-- 13whereg=twiceplusThree
Explicitly,
twice=.adverb:'u u y'plusthree=.verb:'y + 3'g=.plusthreetwiceg713
or tacitly,
twice=.^:2plusthree=.+&3g=.plusthreetwiceg713
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}}
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>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
funtwice(f:(Int)->Int):(Int)->Int{return{f(f(it))}}funplusThree(i:Int)=i+3funmain(){valg=twice(::plusThree)println(g(7))// 13}
functiontwice(f)returnfunction(x)returnf(f(x))endendfunctionplusThree(i)returni+3endlocalg=twice(plusThree)print(g(7))-- 13
functionresult=twice(f)result=@(x)f(f(x));endplusthree=@(i)i+3;g=twice(plusthree)disp(g(7));% 13
lettwicefx=f(fx)letplus_three=(+)3let()=letg=twiceplus_threeinprint_int(g7);(* 13 *)print_newline()
<?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 theuse keyword to do the same.
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
>>>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 functiong could be implemented equivalently:
>>>@twice...defg(i):...returni+3>>>g(7)13
twice<-\(f)\(x)f(f(x))plusThree<-function(i)i+3g<-twice(plusThree)>g(7)[1]13
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.
deftwice(f)->(x){f.call(f.call(x))}endplus_three=->(i){i+3}g=twice(plus_three)putsg.call(7)# 13
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}
objectMain{deftwice(f:Int=>Int):Int=>Int=fcomposefdefplusThree(i:Int):Int=i+3defmain(args:Array[String]):Unit={valg=twice(plusThree)print(g(7))// 13}}
(define(composefg)(lambda(x)(f(gx))))(define(twicef)(composeff))(define(plus-threei)(+i3))(defineg(twiceplus-three))(display(g7)); 13(display"\n")
functwice(_f:@escaping(Int)->Int)->(Int)->Int{return{f(f($0))}}letplusThree={$0+3}letg=twice(plusThree)print(g(7))// 13
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).
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 foundhere.
declarefunctionlocal:twice($f,$x){$f($f($x))};declarefunctionlocal:plusthree($i){$i+3};local:twice(local:plusthree#1,7)(: 13 :)
Function pointers in languages such asC,C++,Fortran, andPascal 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;}
Theqsort 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.
In otherimperative 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 calledEval orExecute operations) in the scope of evaluation. There can be significant drawbacks to this approach:
Inobject-oriented programming languages that do not support higher-order functions,objects can be an effective substitute. An object'smethods 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 addedboilerplate code for defining and instantiating an object and its method(s). Languages that permitstack-based (versusheap-based) objects orstructs can provide more flexibility with this method.
An example of using a simple stack based record inFree 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 functiona() takes aTxy record as input and returns the integer value of the sum of the record'sx andy fields (3 + 7).
Defunctionalization can be used to implement higher-order functions in languages that lackfirst-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 viafunction overloading. The overloaded function in this example has the signatureauto apply.
| Types by domain and codomain | |
|---|---|
| Classes/properties | |
| Constructions | |
| Generalizations | |
