Higher-order function

From Wikipedia, the free encyclopedia

In mathematics and computer science, higher-order functions or functionals are functions which do at least one of the following:

  • take one or more functions as an input
  • output a function

In mathematics these 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 generally those with types containing more than one arrow. In functional programming, higher-order functions that return other functions are said to be curried.

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 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 λx.λy.x.

Contents

[edit] Example

This Python script contains the higher-order function g() which takes a function as its first argument and returns a number. This example prints 100 ( = (7+3)×(7+3) ).

def f(x):
    return x + 3
def g(function, x):
    return function(x) * function(x)
print g(f, 7)

And in this example the higher-order function g() takes a number and returns a function.

def g(x):
    return (lambda y: x + y)
a = g(7)

The function a() takes a number and returns that number plus 7. (e.g a(3)=10)

In another example, this Freepascal program takes a function as its first argument also, and prints 100 :

program Example; 
 
type 
  TIntFunc = function(x: Integer): Integer;
 
function F(X: Integer): Integer; 
begin 
  Result := X + 3; 
end;
 
function G(Func: TIntFunc; X: Integer): Integer; 
begin 
  Result := Func(X) * Func(X); 
end;
 
begin  
  writeln(G(@F, 7)); // prints 100
end.

[edit] Alternatives

In limited imperative programming languages, software can 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. Unfortunately there are 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 additional 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.

Objects in the object-oriented programming paradigm can be used as higher order functions – a method of an object acts in many ways like a function, and a method may take objects (containing methods) as arguments or return objects with methods. Objects often carry additional run-time overhead compared to pure functions, however. Language syntax can introduce additional difficulties; an object must be created to hold any parameters that are functions, and any resulting function must also have an associated object. However, languages that offer stack objects or structs (as opposed to just heap based) can make it easier to utilize an object as if it were a function too.

An example of using a simple stack based record in Freepascal 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 number and returns the number plus 7. (e.g a(3)=10)

[edit] See also

[edit] External links