Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, currying is the technique of transforming a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
In computer programming, a parameter is a special kind of variable, used in a subroutine to refer to one of the pieces of data provided as input to the subroutine. These pieces of data are called arguments...
In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
of arguments) in such a way that it can be called as a chain of functions each with a single argument (partial application
Partial application
In computer science, partial application refers to the process of fixing a number of arguments to a function, producing another function of smaller arity...
Moses Ilyich Schönfinkel, also known as Moisei Isai'evich Sheinfinkel , was a Russian logician and mathematician, known for the invention of combinatory logic.- Life :Schönfinkel attended the Novorossiysk University of Odessa, studying mathematics under Samuil Osipovich...
Haskell Brooks Curry was an American mathematician and logician. Curry is best known for his work in combinatory logic; while the initial concept of combinatory logic was based on a single paper by Moses Schönfinkel, much of the development was done by Curry. Curry is also known for Curry's...
Stigler's law of eponymy is a process proposed by University of Chicago statistics professor Stephen Stigler in his 1980 publication "Stigler’s law of eponymy". In its simplest and strongest form it says: "No scientific discovery is named after its original discoverer." Stigler named the...
schönfinkeling.
Uncurrying (also known as counter-currying) is the dual
Duality (mathematics)
In mathematics, a duality, generally speaking, translates concepts, theorems or mathematical structures into other concepts, theorems or structures, in a one-to-one fashion, often by means of an involution operation: if the dual of A is B, then the dual of B is A. As involutions sometimes have...
transformation to currying, and can be seen as a form of defunctionalization
Defunctionalization
In programming languages, defunctionalization refers to a compile-time transformation which eliminates higher-order functions, replacing them by a single first-order apply function. The technique was first described by John C. Reynolds in his 1972 paper, "Definitional Interpreters for Higher-Order...
. 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.
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 :
To evaluate , first replace with 2.
Since the result is a function of , this function can be defined as .
Next, replace the argument with 3, producing .
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
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
, and multi-argument functions are usually represented in curried form.
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
s almost always use curried functions to achieve multiple arguments; notable examples are ML
ML programming language
ML is a general-purpose functional programming language developed by Robin Milner and others in the early 1970s at the University of Edinburgh, whose syntax is inspired by ISWIM...
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
, where in both cases all functions have exactly one argument.
This is similar in computer code:
If we let f be a function f(x,y) = y / x
then the function g g x = \y -> f(x,y)
is a curried version of f. In particular, g 2 = \y -> f(2,y)
is the curried equivalent of the example above. Though note that currying, while similar, is not the same operation as partial function application.
Definition
Given a function f of type , currying it makes a function . That is, takes an argument of type and returns a function of type . Uncurrying is the reverse transformation, and is most easily understood in terms of its right adjoint, apply
Apply
In mathematics and computer science, Apply is a function that applies functions to arguments. It is central to programming languages derived from lambda calculus, such as LISP and Scheme, and also in functional languages...
.
The → operator is often considered right-associative, so the curried function type is often written as . Conversely, function application
Function application
In mathematics, function application is the act of applying a function to an argument from its domain so as to obtain the corresponding value from its range.-Representation:...
is considered to be left-associative, so that is equivalent to .
Curried functions may be used in any language that supports closure
Closure (computer science)
In computer science, a closure is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables outside its typical scope. Such a function is said to be "closed over" its free variables...
s; 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.
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
, currying provides a way to study functions with multiple arguments in very simple theoretical models such as the lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
in which functions only take a single argument.
In a set-theoretic paradigm, currying is the natural correspondence between the set of functions from to , and the set of functions from to the set of functions from to . In category theory
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
In various branches of mathematics, a useful construction is often viewed as the “most efficient solution” to a certain problem. The definition of a universal property uses the language of category theory to make this notion precise and to study it abstractly.This article gives a general treatment...
In mathematics, specifically in category theory, an exponential object is the categorical equivalent of a function space in set theory. Categories with all finite products and exponential objects are called cartesian closed categories...
In category theory, a category is cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in mathematical logic and the theory of programming, in...
In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure of the categories involved. Hence, a natural transformation can be considered to be a "morphism of functors". Indeed this intuition...
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations. If there exists an isomorphism between two structures, the two structures are said to be isomorphic. In a certain sense, isomorphic structures are...
In category theory, the product of two objects in a category is a notion designed to capture the essence behind constructions in other areas of mathematics such as the cartesian product of sets, the direct product of groups, the direct product of rings and the product of topological spaces...
and the morphisms to an exponential object . In other words, currying is the statement that product
Product (category theory)
In category theory, the product of two objects in a category is a notion designed to capture the essence behind constructions in other areas of mathematics such as the cartesian product of sets, the direct product of groups, the direct product of rings and the product of topological spaces...
In mathematics, specifically in category theory, hom-sets, i.e. sets of morphisms between objects, give rise to important functors to the category of sets. These functors are called hom-functors and have numerous applications in category theory and other branches of mathematics.-Formal...
In mathematics, adjoint functors are pairs of functors which stand in a particular relationship with one another, called an adjunction. The relationship of adjunction is ubiquitous in mathematics, as it rigorously reflects the intuitive notions of optimization and efficiency...
In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure of the categories involved. Hence, a natural transformation can be considered to be a "morphism of functors". Indeed this intuition...
In category theory, a category is cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in mathematical logic and the theory of programming, in...
.
Under the Curry-Howard correspondence, the existence of currying and uncurrying is equivalent to the logical theorem , as tuple
Tuple
In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
In programming languages and type theory, a product of types is another, compounded, type in a structure. The "operands" of the product are types, and the structure of a product type is determined by the fixed order of the operands in the product. An instance of a product type retains the fixed...
) corresponds to conjunction in logic, and function type corresponds to implication.
In mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...
Christopher Strachey was a British computer scientist. He was one of the founders of denotational semantics, and a pioneer in programming language design...
Haskell Brooks Curry was an American mathematician and logician. Curry is best known for his work in combinatory logic; while the initial concept of combinatory logic was based on a single paper by Moses Schönfinkel, much of the development was done by Curry. Curry is also known for Curry's...
. The alternative name "Schönfinkelisation", has been proposed as a reference to Moses Schönfinkel
Moses Schönfinkel
Moses Ilyich Schönfinkel, also known as Moisei Isai'evich Sheinfinkel , was a Russian logician and mathematician, known for the invention of combinatory logic.- Life :Schönfinkel attended the Novorossiysk University of Odessa, studying mathematics under Samuil Osipovich...
.
Contrast with partial function application
Currying and partial function application are often conflated. The difference between the two is clearest for functions taking more than two arguments.
Given a function of type , currying produces . That is, while an evaluation of the first function might be represented as , evaluation of the curried function would be represented as , applying each argument in turn to a single-argument function returned by the previous invocation. Note that after calling , 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 above, we might fix (or 'bind') the first argument, producing a function of type . Evaluation of this function might be represented as . 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 argument
Parameter (computer science)
In computer programming, a parameter is a special kind of variable, used in a subroutine to refer to one of the pieces of data provided as input to the subroutine. These pieces of data are called arguments...
s 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.
In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
In computer science, a closure is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables outside its typical scope. Such a function is said to be "closed over" its free variables...
The Portland Pattern Repository is a repository for computer programming design patterns. It was accompanied by a companion website, WikiWikiWeb, which was the world's first wiki....
:
, currying it makes a function 
. That is, 
takes an argument of type 
and returns a function of type 
. Uncurrying is the reverse transformation, and is most easily understood in terms of its right adjoint, apply
is often written as 
. Conversely, function application
is equivalent to 
.
of functions from 
to 
, and the set 
of functions from 
to the set of functions from 
to 
. In category theory
and the morphisms to an exponential object 
. In other words, currying is the statement that product
, as tuple
, currying produces 
. That is, while an evaluation of the first function might be represented as 
, evaluation of the curried function would be represented as 
, applying each argument in turn to a single-argument function returned by the previous invocation. Note that after calling 
, we are left with a function that takes a single argument and returns another function, not a function that takes two arguments.
above, we might fix (or 'bind') the first argument, producing a function of type 
. Evaluation of this function might be represented as 
. Note that the result of partial function application in this case is a function that takes two arguments.
, first replace 
with 2.
, this function 
can be defined as 
.
argument with 3, producing 
.