# Higher-order function

(Redirected from Higher-order functions)

In mathematics and computer science, a higher-order function (also functional form, functional or functor) is a function that does at least one of the following:

• takes one or more functions as an input
• outputs a function

All other functions are first-order functions. In mathematics higher-order functions are also known as operators or functionals. The derivative in calculus is a common example, since it maps a function to another function.

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 are values with types of the form $(\tau_1\to\tau_2)\to\tau_3$.

The 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 list of elements, and as the result, returns a new list with f applied to each element from the list. Another very common kind of higher-order function in those languages which support them are 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.

Other examples of higher-order functions include fold, function composition, integration, and the constant-function function λxy.x.

## Example

The following examples are not intended to compare and contrast programming languages, since each program performs a different task.

This Python program defines the higher-order function twice which takes a function and an arbitrary object (here a number), and applies the function to the object twice. This example prints 13: twice(f, 7) = f(f(7)) = (7 + 3) + 3.

def f(x):
return x + 3

def twice(function, x):
return function(function(x))

print(twice(f, 7))


This Haskell code is the equivalent of the Python program above.

f = (+3)
twice function = function . function
main = print (twice f 7)


In this Scheme example the higher-order function g() takes a number and returns a function. The function a() takes a number and returns that number plus 7 (e.g. a(3)=10).

(define (g x)
(lambda (y) (+ x y)))
(define a (g 7))
(display (a 3))


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.

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


In this JavaScript example the higher-order function ArrayForEach takes an array and a method in as arguments and calls the method on every element in the array. That is, it Maps the function over the array elements.

function ArrayForEach(array, func) {
for (var i = 0; i < array.length; i++) {
if (i in array) {
func(array[i]);
}
}
}

function log(msg) {
console.log(msg);
}

ArrayForEach([1,2,3,4,5], log);


this could also be implemeted as

function log(msg) {
console.log(msg);
}

[1,2,3,4,5].map(log);


This JavaScript code is the equivalent of the Python program above:

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

return x+3;
}



This Ruby code is the equivalent of the Python program above.

f1 = ->(x){ x + 3 }
def twice(f, x); f.call(f.call(x)) end

print twice(f1, 7)


## Alternatives

### Function Pointers

Function pointers 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:

#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) {
double sum = 0, dt = (b - a) / n;
for (int 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;
}


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 through use of 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:

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.


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