# Currying

{{#invoke:Hatnote|hatnote}} In mathematics and computer science, currying is the technique of translating the evaluation of a function that takes multiple arguments (or a tuple of arguments) into evaluating a sequence of functions, each with a single argument (partial application). It was introduced by Moses Schönfinkel[1][2][3] and later developed by Haskell Curry.[4][5]

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

## 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 ${\displaystyle f(x,y)=y/x}$:

To evaluate ${\displaystyle f(2,3)}$, first replace ${\displaystyle x}$ with ${\displaystyle 2}$
Since the result is a function of ${\displaystyle y}$, this new function ${\displaystyle g(y)}$ can be defined as ${\displaystyle g(y)=f(2,y)=y/2}$
Next, replace the ${\displaystyle y}$ argument with ${\displaystyle 3}$, producing ${\displaystyle 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

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

then the function h where

${\displaystyle h(x)=y\mapsto f(x,y)}$

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

${\displaystyle g(y)=h(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 ${\displaystyle \scriptstyle f}$ of type ${\displaystyle \scriptstyle f\colon (X\times Y)\to Z}$, currying it makes a function ${\displaystyle \scriptstyle {\text{curry}}(f)\colon X\to (Y\to Z)}$. That is, ${\displaystyle \scriptstyle {\text{curry}}(f)}$ takes an argument of type ${\displaystyle \scriptstyle X}$ and returns a function of type ${\displaystyle \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 ${\displaystyle \scriptstyle X\to (Y\to Z)}$ is often written as ${\displaystyle \scriptstyle X\to Y\to Z}$. Conversely, function application is considered to be left-associative, so that ${\displaystyle \scriptstyle f\;\langle x,y\rangle }$ is equivalent to ${\displaystyle \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 ${\displaystyle \scriptstyle A^{B\times C}}$ of functions from ${\displaystyle \scriptstyle B\times C}$ to ${\displaystyle A}$, and the set ${\displaystyle \scriptstyle \left(A^{C}\right)^{B}}$ of functions from ${\displaystyle \scriptstyle B}$ to the set of functions from ${\displaystyle \scriptstyle C}$ to ${\displaystyle \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 ${\displaystyle \scriptstyle f\colon (X\times Y)\to Z}$ and the morphisms to an exponential object ${\displaystyle \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:

${\displaystyle \hom(A\times B,C)\cong \hom(A,C^{B}).}$

This is the key property of being a Cartesian closed category, and more generally, a closed monoidal category.[6] The latter, though more rarely discussed, is interesting, as it is the suitable setting for quantum computation,[7] whereas the former is sufficient for classical logic. The difference is that the Cartesian product can be interpreted simply as a pair of items (or a list), whereas the tensor product, used to define a monoidal category, is suitable for describing entangled quantum states.[8]

Under the Curry–Howard correspondence, the existence of currying and uncurrying is equivalent to the logical theorem ${\displaystyle \scriptstyle (A\land 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.[9]

## 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.[10]

## Contrast with partial function application

{{#invoke:main|main}} Currying and partial function application are often conflated.[11] One of the significant differences between the two is that a call to a partially applied function returns the result right away, not another function down the currying chain; this distinction can be illustrated clearly for functions whose arity is greater than two.[12]

Given a function of type ${\displaystyle \scriptstyle f\colon (X\times Y\times Z)\to N}$, currying produces ${\displaystyle \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 ${\displaystyle \scriptstyle f(1,2,3)}$, evaluation of the curried function would be represented as ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \scriptstyle f}$ above, we might fix (or 'bind') the first argument, producing a function of type ${\displaystyle \scriptstyle {\text{partial}}(f)\colon (Y\times Z)\to N}$. Evaluation of this function might be represented as ${\displaystyle \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.

## Notes

1. {{#invoke:Citation/CS1|citation |CitationClass=journal }} (Reprinted lecture notes from 1967.)
2. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
3. Kenneth Slonneger and Barry L. Kurtz. Formal Syntax and Semantics of Programming Languages. p. 144.
4. Henk Barendregt, Erik Barendsen, "Introduction to Lambda Calculus", March 2000, page 8.
5. {{#invoke:citation/CS1|citation |CitationClass=book }}
6. Template:Nlab
7. Samson Abramsky and Bob Coecke, "A Categorical Semantics for Quantum Protocols", "[1].
8. John c. Baez and Mike Stay, "Physics, Topology, Logic and Computation: A Rosetta Stone", (2009) ArXiv 0903.0340 in New Structures for Physics, ed. Bob Coecke, Lecture Notes in Physics vol. 813, Springer, Berlin, 2011, pp. 95-174.
9. {{#invoke:citation/CS1|citation |CitationClass=book }} (See theorems 1.2.13, 1.2.14)
10. I. Heim and A. Kratzer (1998). Semantics in Generative Grammar. Blackwell.
11. Partial Function Application is not Currying
12. Functional Programming in 5 Minutes

## References

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}