Higher-order function

From Wikipedia, the free encyclopedia
  (Redirected from First order functions)
Jump to: navigation, search

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[edit]

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));
}
 
function add3(x){
    return x+3;
}
 
twice(add3, 7); // 13

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[edit]

In programming languages that support function pointers, one can emulate higher-order functions to some extent. Such languages include the C and C++ family. An example is the following C code which computes an approximation of the integral of an arbitrary function:

#include<stdio.h>
 
double integral(double f(double x), double a, double b, int n)
{ /* Compute the integral of f() within the interval [a,b] */
  double sum = 0, dt = (b - a) / n;
  for (int i = 0;  i < n;  i++) sum += f(a+(i+.5)*dt);
  return sum * dt;
}
 
double f(double x) {return 3*x*x;}
 
int main(){
  printf("%g\n",integral(f,0,1,100));
  return 0;
}

Another example is the function qsort from C standard library.

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.

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

See also[edit]

External links[edit]