Headline

Transformation of a function on multiple arguments to take one at a time

Illustration

In Language:Haskell, functions are typically in curried form. Consider, for example, the signature of addition:

> :t (+)
(+) :: Num a => a -> a -> a

Curried form is generally convenient as it directly enables partial application. For instance, we can define an increment function, just by passing one argument to addition:

inc :: Int -> Int
inc = (+) 1

If we were to define addition in uncurried form, then this would look as follows:

add :: Num a => (a, a) -> a
add (x,y) = x+y

We can easily perform currying:

add' :: Num a => a -> a -> a
add' x y = add (x,y)

In fact, the currying transformation can be represented by the following higher-order function:

curry :: ((a, b) -> c) -> a -> b -> c
curry f a b = f (a,b)

(We would need such a curry(ing) function for each number of arguments.) Thus, we can express the currying transformation as follows:

add'' :: Num a => a -> a -> a
add'' = curry add

Relationships

See uncurrying for the dual transformation.

Citation

(http://en.wikipedia.org/wiki/Currying, 18 May 2013)

In mathematics and computer science, currying is the technique of transforming a function that takes multiple arguments (or a tuple of arguments) in such a way that it can be called as a chain of functions, each with a single argument (partial application). It was originated by Moses Schönfinkel ... and later re-discovered by Haskell Curry.

Headline

Transformation of a function to take its multiple arguments at once

Illustration

In Language:Haskell, functions are typically in curried form. Consider, for example, the signature of addition:

> :t (+)
(+) :: Num a => a -> a -> a

Thus, addition takes one argument at a time. If we were to define addition in uncurried form, then this would look as follows:

add :: Num a => (a, a) -> a
add (x,y) = x + y

In fact, the uncurrying transformation can be represented by the following higher-order function:

uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry f (a,b) = f a b

(We would need such an uncurry(ing) function for each number of arguments.) Thus, we can express the uncurrying transformation as follows:

add' :: Num a => (a, a) -> a
add' = uncurry (+)

Relationships

See currying for the dual transformation.

Citation

(http://en.wikipedia.org/wiki/Currying, 18 May 2013)

Uncurrying is the dual transformation to currying, and can be seen as a form of defunctionalization. It takes a function f(x) which returns another function g(y) as a result, and yields a new function f′(x,y) which takes a number of additional parameters and applies them to the function returned by function f.

Headline

A Function that takes as an argument or returns a function

Illustration

A higher-order function is a function that takes functions as arguments or returns functions as results. Consider the following Language:Haskell function which applies a given argument function twice:

twice :: (x -> x) -> x -> x
twice f = f . f

For instance:

> twice (+1) 40
42

twice is clearly a higher-order function in that its first argument is of a function type "x -> x". twice is actually also a higher-order function in that it composes a function that it returns as result, namely "f . f". The function composition operator "." is another higher-order function, which is obvious from its type, again:

> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

For what it matters, the type itself already reveals that the second function is applied before the first function because of how type "a" of the third argument equals with the argument type of the second function, etc. Now it would be straightforward to define function composition (except that we do not need to do, as it is predefined evidently):

(.) f g x = f (g x)

See list processing functions such as map, fold, and filter for more examples of higher-order functions. See the concept of currying as well.

Headline

Apply a function to some but not all arguments

Illustration

Here is an example of "non-partial" application of addition in Language:Haskell:

> 41 + 1
42

In this example, we actually increment 41. Let us thus define the increment function as a partial application of addition so that we can model the same computation as follows:

> let inc = (+) 1
> inc 41
42

It is important that "+" was surrounded by "(...)" because "+" is an infix operator and we need to use in an prefix manner when aiming at partial application. The notation "(+)" does indeed produce a prefix operator.

In Haskell, sections for infix operators correspond to a special form of partial application. A section applies an infix operator to one of its two operands by using parenthesization in the following way:

> let inc = (+1)
> inc 41
42

In this example, we have applied "+" to its second operand. For what it matters (and because addition is commutative), we could also define the increment function in terms of a section for the first operand:

> let inc = (1+)
> inc 41
42

Discussion

In languages with type-level functions such as parametrized type synonyms or data types, e.g., Language:Haskell, partial application makes sense at the type level as well.

Headline

The functional programming language Haskell

Details

101wiki hosts plenty of Haskell-based contributions. This is evident from corresponding back-links. More selective sets of Haskell-based contributions are organized in themes: Theme:Haskell data, Theme:Haskell potpourri, and Theme:Haskell genericity. Haskell is also the language of choice for a course supported by 101wiki: Course:Lambdas_in_Koblenz.

Illustration

The following expression takes the first 42 elements of the infinite list of natural numbers:

> take 42 [0..]
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41]

In this example, we leverage Haskell's lazy evaluation.