Newton's law of universal gravitation

2014-01-31T23:35:57Z

62.56.70.148: /* Extensions */ typo

{{merge from|Procedural parameter|date=May 2012}}
{{inline citations|date=September 2013}}
In [[mathematics]] and [[computer science]], a '''higher-order function''' (also '''functional form''', '''functional''' or '''functor''') is a [[function (mathematics)|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 ''[[operator (mathematics)|operators]]'' or ''[[functional (mathematics)|functionals]]''. The [[derivative]] in [[calculus]] is a common example, since it maps a function to another function.

In the [[lambda calculus|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 <math>(\tau_1\to\tau_2)\to\tau_3</math>.

The <code>[[map (higher-order function)|map]]</code> 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 (programming language)|C]] standard [[function (computer science)|function]] <code>qsort</code> is an example of this.

Other examples of higher-order functions include [[fold (higher-order function)|fold]], [[function composition (computer science)|function composition]], [[integral|integration]], and the constant-function function λ''x''.λ''y''.''x''.

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

This [[Python (programming language)|Python]] program defines the higher-order function <code>twice</code> 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.
<source lang="python">
def f(x):
return x + 3

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

print(twice(f, 7))
</source>
This [[Haskell (programming language)|Haskell]] code is the equivalent of the Python program above.
<source lang="haskell">
f = (+3)
twice function = function . function
main = print (twice f 7)
</source>
In this [[Scheme (programming language)|Scheme]] example the higher-order function <code>g()</code> takes a number and returns a function. The function <code>a()</code> takes a number and returns that number plus 7 (e.g. ''a''(3)=10).
<source lang="scheme">
(define (g x)
(lambda (y) (+ x y)))
(define a (g 7))
(display (a 3))
</source>

In this [[Erlang (programming language)|Erlang]] example the higher-order function <code>or_else</code>/2 takes a list of functions (<code>Fs</code>) and argument (<code>X</code>). It evaluates the function <code>F</code> with the argument <code>X</code> as argument. If the function <code>F</code> returns false then the next function in <code>Fs</code> will be evaluated. If the function <code>F</code> returns <code>{false,Y}</code> then the next function in <code>Fs</code> with argument <code>Y</code> will be evaluated. If the function <code>F</code> returns <code>R</code> the higher-order function <code>or_else</code>/2 will return <code>R</code>. Note that <code>X</code>, <code>Y</code>, and <code>R</code> can be functions. The example returns <code>false</code>.
<source lang="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([fun erlang:is_integer/1, fun erlang:is_atom/1, fun erlang:is_list/1],3.23).
</source>

In this [[JavaScript]] example the higher-order function <code>ArrayForEach</code> takes an array and a method in as arguments and calls the method on every element in the array. That is, it [[Map (higher-order function)|Map]]s the function over the array elements.
<source lang="javascript">
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);
</source>

This [[Ruby (programming language)|Ruby ]] code is the equivalent of the Python program above.
<source lang="ruby">
f1 = ->(x){ x + 3 }
def twice(f, x); f.call(f.call(x)) end

print twice(f1, 7)
</source>

==Alternatives==

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

<source lang=c>
// Compute the integral of f() within the interval [a,b]
double integral(double (*f)(double x), double a, double b)
{
double sum, dt;
int i;

// Numerical integration: 0th order approximation
sum = 0.0;
dt = (b - a) / 100.0;
for (i = 0; i < 100; i++)
sum += (*f)(i * dt + a) * dt;

return sum;
}
</source>

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 [[type system#Static typing|statically typed]]; these languages generally rely on [[type system#Dynamic typing|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 [[interpreter (computing)|interpretation]], causing some added overhead at run-time, and usually generating less efficient code.

[[Macro (computer science)|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, [[object (computer science)|objects]] can be an effective substitute. An object's [[method (computer science)|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 memory allocation|stack]]-based (versus [[dynamic memory allocation|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:

<source lang=pascal>
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.
</source>

The function <code>a()</code> takes a <code>Txy</code> record as input and returns the integer value of the sum of the record's <code>x</code> and <code>y</code> fields (3 + 7).

==See also==
*[[First-class function]]
*[[Combinatory logic]]
*[[Function-level programming]]
*[[Functional programming]]
*[[Kappa calculus]] - a formalism for functions which ''excludes'' higher-order functions
*[[Strategy pattern]]
*[[Higher order message]]s

==External links==
*[http://ergodicity.iamganesh.com/2006/08/07/higher-order-functions/ Higher-order functions and variational calculus]
*[http://boost.org/doc/html/lambda.html Boost Lambda Library for C++]
*[http://hop.perl.plover.com/book/ Higher Order Perl]

[[Category:Functional programming]]
[[Category:Lambda calculus]]
[[Category:Higher-order functions| ]]
[[Category:Subroutines]]
[[Category:Articles with example Python code]]
[[Category:Articles with example Haskell code]]
[[Category:Articles with example Scheme code]]
[[Category:Articles with example Erlang code]]
[[Category:Articles with example JavaScript code]]
[[Category:Articles with example C code]]
[[Category:Articles with example Pascal code]]

formulasearchengine - User contributions [en]

Newton's law of universal gravitation