Search: in
Currying
Currying in Encyclopedia Encyclopedia
  Tutorials     Encyclopedia     Videos     Books     Software     DVDs  
       





Currying

In mathematics and computer science, currying is the technique of transforming a function that takes multiple arguments (or an n-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 discovered by Moses Sch nfinkel[1] and later re-discovered by Haskell Curry.[2] Because of this, some say it would be more correct to name it sch nfinkeling.[3][4]

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 f. The process can be iterated if necessary.

Contents


Motivation

Currying is similar to the process of calculating a function of multiple variables for some given values on paper. For example, given the function \scriptstyle f(x,y) = y / x:

To evaluate \scriptstyle f(2,3), first replace \scriptstyle x with 2.
Since the result is a function of \scriptstyle y, this function \scriptstyle g(y) can be defined as \scriptstyle g(y) = f(2,y) = y/2.
Next, replace the \scriptstyle y argument with 3, producing \scriptstyle g(3) = f(2,3) = 3/2.

On paper, using classical notation, this is usually done all in one step. However, each argument can be replaced sequentially as well. Each replacement results in a function taking exactly one argument. This produces a chain of functions as in lambda calculus, and multi-argument functions are usually represented in curried form.

Some programming languages almost always use curried functions to achieve multiple arguments; notable examples are ML and Haskell, where in both cases all functions have exactly one argument.

If we let f be a function

f(x,y) = \frac{y}{x}

then the function g

g(x) = y \mapsto f(x,y)

is a curried version of f. Here, \scriptstyle y \mapsto z is a function that maps an argument y to result z. In particular,

g(2) = y \mapsto f(2,y)

is the curried equivalent of the example above. Note, however, that currying, while similar, is not the same operation as partial function application.

Definition

Given a function f of type \scriptstyle f \colon (X \times Y) \to Z , currying it makes a function \scriptstyle \text{curry}(f) \colon X \to (Y \to Z) . That is, \scriptstyle \text{curry}(f) takes an argument of type \scriptstyle X and returns a function of type \scriptstyle Y \to Z . Uncurrying is the reverse transformation, and is most easily understood in terms of its right adjoint, apply.

The operator is often considered right-associative, so the curried function type \scriptstyle X \to (Y \to Z) is often written as \scriptstyle X \to Y \to Z. Conversely, function application is considered to be left-associative, so that \scriptstyle f \; \langle x, y \rangle is equivalent to \scriptstyle\text{curry}(f) \; x \; y.

Curried functions may be used in any language that supports closures; however, uncurried functions are generally preferred for efficiency reasons, since the overhead of partial application and closure creation can then be avoided for most function calls.

Mathematical view

In theoretical computer science, currying provides a way to study functions with multiple arguments in very simple theoretical models such as the lambda calculus in which functions only take a single argument.

In a set-theoretic paradigm, currying is the natural correspondence between the set \scriptstyle A^{B\times C} of functions from \scriptstyle B\times C to A, and the set \scriptstyle\left(A^B\right)^C of functions from \scriptstyle C to the set of functions from \scriptstyle B to \scriptstyle A. In category theory, currying can be found in the universal property of an exponential object, which gives rise to the following adjunction in cartesian closed categories: There is a natural isomorphism between the morphisms from a binary product \scriptstyle f \colon (X \times Y) \to Z and the morphisms to an exponential object \scriptstyle g \colon X \to Z^Y . In other words, currying is the statement that product and Hom are adjoint functors; that is there is a natural transformation:

\hom(A\times B, C) \cong \hom(A, C^B) .

This is the key property of being a Cartesian closed category.

Under the Curry Howard correspondence, the existence of currying and uncurrying is equivalent to the logical theorem \scriptstyle (A \and B) \to C \Leftrightarrow A \to (B \to C), as tuples (product type) corresponds to conjunction in logic, and function type corresponds to implication.

Curry is a continuous function in the Scott topology.[5]

Naming

The name "currying", coined by Christopher Strachey in 1967, is a reference to logician Haskell Curry. The alternative name "Sch nfinkelisation", has been proposed as a reference to Moses Sch nfinkel.[6]

Contrast with partial function application

Currying and partial function application are often conflated.[7] The difference between the two is clearest for functions taking more than two arguments.

Given a function of type \scriptstyle f \colon (X \times Y \times Z) \to N , currying produces \scriptstyle \text{curry}(f) \colon X \to (Y \to (Z \to N)) . That is, while an evaluation of the first function might be represented as \scriptstyle f(1, 2, 3), evaluation of the curried function would be represented as \scriptstyle f_\text{curried}(1)(2)(3), applying each argument in turn to a single-argument function returned by the previous invocation. Note that after calling \scriptstyle f_\text{curried}(1), we are left with a function that takes a single argument and returns another function, not a function that takes two arguments.

In contrast, partial function application refers to the process of fixing a number of arguments to a function, producing another function of smaller arity. Given the definition of \scriptstyle f above, we might fix (or 'bind') the first argument, producing a function of type \scriptstyle\text{partial}(f) \colon (Y \times Z) \to N. Evaluation of this function might be represented as \scriptstyle f_\text{partial}(2, 3). Note that the result of partial function application in this case is a function that takes two arguments.

Intuitively, partial function application says "if you fix the first arguments of the function, you get a function of the remaining arguments". For example, if function div stands for the division operation x/y, then div with the parameter x fixed at 1 (i.e., div 1) is another function: the same as the function inv that returns the multiplicative inverse of its argument, defined by inv(y) = 1/y.

The practical motivation for partial application is that very often the functions obtained by supplying some but not all of the arguments to a function are useful; for example, many languages have a function or operator similar to plus_one. Partial application makes it easy to define these functions, for example by creating a function that represents the addition operator with 1 bound as its first argument.

See also

  • Lazy evaluation
  • Closure (computer science)
  • smn theorem
  • Closed monoidal category

Notes

References

External links

ca:Currificaci de:Currying es:Currificaci n fr:Curryfication it:Applicazione parziale he: ja: pl:Currying pt:Currying ru: zh:






Source: Wikipedia | The above article is available under the GNU FDL. | Edit this article



Search for Currying in Tutorials
Search for Currying in Encyclopedia
Search for Currying in Videos
Search for Currying in Books
Search for Currying in Software
Search for Currying in DVDs
Search for Currying in Store




Advertisement




Currying in Encyclopedia
Currying top Currying

Home - Add TutorGig to Your Site - Disclaimer

©2011-2013 TutorGig.info All Rights Reserved. Privacy Statement