Currying: Information from Answers.com

This article is about the function transformation technique. For the general variety of spicy dishes from India and other Asian countries, see Curry. For the electrical retailer in the United Kingdom, see Currys.

In mathematics and computer science, currying or Schönfinkelisation, invented by Moses Schönfinkel and later re-invented by Haskell Curry,^[1] 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.

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.

1 Motivation
2 Definition
3 Mathematical view
4 Naming
5 See also
6 Notes
7 References
8 External links

Motivation

Currying is actually not very different from what we do when we calculate a function for some given values on a piece of paper.

Take the function

f (x, y) = y / x

To evaluate

f (2,3)

, first, replace

x

with 2.

Since the result is a new function in

y

, this function

g (y)

can be defined as

g (y) = f (2, y) = y / 2

Next, replacing the

y

argument with 3,

provides the result,

g (3) = f (2,3) = 3 / 2

On paper, using classical notation, it's just that we seem to do it all at the same time. But, in fact, when replacing arguments on a piece of paper, it is done sequentially (i.e.partially). Each replacement results in a function within a function. As we sequentially replace each argument, we are currying the function into simpler and simpler versions of the original. Eventually, we end up with a chain of functions as in lambda calculus, where each function takes only one argument, and multi-argument functions are usually represented in curried form.

The practical motivation for currying is that very often the functions obtained by supplying some but not all of the arguments to a curried function (often called partial application) are useful; for example, many languages have a function or operator similar to plus_one. Currying makes it easy to define these functions.

This is similar in computer code: If we let f be a function

f (x,y) = y / x

then the function

g x = (\y -> f (x,y))

is a curried version of f. In particular

(g 2) = (\y -> f (2,y))

is the version from the paper example.

Definition

Given a function f of type $f \colon (X \times Y) \to Z$ , then currying it makes a function $\mbox{curry}(f) \colon X \to (Y \to Z)$ . That is, $curry(f)$ takes an argument of type $X$ and returns a function of type $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 $X \to (Y \to Z)$ is often written as $X \to Y \to Z$ . Conversely, function application is considered to be left-associative, so that $f \; \langle x, y \rangle$ is equivalent to $\mbox{curry}(f) \; x \; y$ .

Intuitively, currying 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 curried form of 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.

Some programming languages have built-in syntactic support for currying, where what looks like a multi-argument function is actually syntactic sugar for the function in curried form; notable examples are ML and Haskell, where in both cases all functions have exactly one argument.

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.

When viewed in a set-theoretic light, currying becomes the theorem that the set $A^{B\times C}$ of functions from $B\times C$ to $A$ , and the set $(A B) C$ of functions from $C$ to the set of functions from $B$ to $A$ , are isomorphic. 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 $f \colon (X \times Y) \to Z$ and the morphisms to an exponential object $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,\hom(B,C)) .$

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 $(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.

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.^[2]