Higher order function

This article or the following section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

A higher order function ( English higher-order function ) is in computer science , a function gets that functions as arguments and / or provides functions as a result.

The term is used in particular in the lambda calculus , the theoretical basis of functional programming . There it is closely linked to currying , a procedure that converts functions with several arguments into several one-parameter functions. This transformation is based on the fact that the function spaces and with each other can be identified for any set . ${\displaystyle A,B,C}$ ${\displaystyle A\times B\to C}$ ${\displaystyle A\to (B\to C)}$

The following function is a higher order function:

${\displaystyle f\colon \mathbb {R} \to (\mathbb {N} \to \mathbb {R} ),x\mapsto (m\mapsto x+m)}$

This function maps each value to a function that adds a (transferred) natural number . For example . is shown in turn on : ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle f(10{,}5)=(m\mapsto 10{,}5+m)}$ ${\displaystyle m}$ ${\displaystyle x+m}$ ${\displaystyle (f(10{,}5))(1)=11{,}5}$

The K combiner comes from the lambda calculus . is constant for everyone . ${\displaystyle K=(x\mapsto (y\mapsto x))}$ ${\displaystyle (K(x))(y)}$ ${\displaystyle y}$

A well-known example of a higher order function is the differential operator , because it maps functions to functions (derivative and antiderivative). Other important examples are the so-called distributions . In the case with is a - vector space and is therefore a functional . ${\displaystyle f:(A\to \mathbb {K} )\to \mathbb {K} }$ ${\displaystyle \mathbb {K} \in \{\mathbb {R} ,\mathbb {C} \}}$ ${\displaystyle A\to \mathbb {K} }$ ${\displaystyle \mathbb {K} }$ ${\displaystyle f}$

Example from functional programming

In most functional programming languages ​​such as B. Haskell , the higher order mapfunction can be defined. It takes a function as an argument fand returns a function that fapplies to every element of a passed list. It should be noted that mapfunctions of any type can be given as arguments (indicated by the type variables aand b).

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = (f x):map f xs

map (\x -> x ^ 2) [1, 2, 3, 4] -- wird ausgewertet zu [1, 4, 9, 16]

Web links

• Simon Thompson: Type Theory and Functional Programming . (PDF; 1.3 MB)