In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
and
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, currying is the technique of translating a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-orie ...
that takes multiple
arguments
An argument is a series of sentences, statements, or propositions some of which are called premises and one is the conclusion. The purpose of an argument is to give reasons for one's conclusion via justification, explanation, and/or persua ...
into a sequence of families of functions, each taking a single argument.
In the prototypical example, one begins with a function
that takes two arguments, one from
and one from
and produces objects in
The curried form of this function treats the first argument as a parameter, so as to create a family of functions
The family is arranged so that for each object
in
there is exactly one function
In this example,
itself becomes a function that takes
as an argument, and returns a function that maps each
to
The proper notation for expressing this is verbose. The function
belongs to the set of functions
Meanwhile,
belongs to the set of functions
Thus, something that maps
to
will be of the type
With this notation,
is a function that takes objects from the first set, and returns objects in the second set, and so one writes
This is a somewhat informal example; more precise definitions of what is meant by "object" and "function" are given below. These definitions vary from context to context, and take different forms, depending on the theory that one is working in.
Currying is related to, but not the same as,
partial application
Partial may refer to:
Mathematics
*Partial derivative, derivative with respect to one of several variables of a function, with the other variables held constant
** ∂, a symbol that can denote a partial derivative, sometimes pronounced "partial ...
.
The example above can be used to illustrate partial application; it is quite similar. Partial application is the function
that takes the pair
and
together as arguments, and returns
Using the same notation as above, partial application has the signature
Written this way, application can be seen to be adjoint to currying.
The currying of a function with more than two arguments can be defined by induction.
Currying is useful in both practical and theoretical settings. In
functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declarat ...
languages
Language is a structured system of communication that consists of grammar and vocabulary. It is the primary means by which humans convey meaning, both in spoken and signed forms, and may also be conveyed through writing. Human language is ch ...
, and many others, it provides a way of automatically managing how arguments are passed to functions and exceptions. In
theoretical computer science
Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation.
It is difficult to circumscribe the theoretical areas precisely. The Associati ...
, it provides a way to study functions with multiple arguments in simpler theoretical models which provide only one argument. The most general setting for the strict notion of currying and uncurrying is in the
closed monoidal categories, which underpins a vast generalization of the
Curry–Howard correspondence
In programming language theory and proof theory, the Curry–Howard correspondence is the direct relationship between computer programs and mathematical proofs. It is also known as the Curry–Howard isomorphism or equivalence, or the proofs-as-p ...
of proofs and programs to a correspondence with many other structures, including quantum mechanics, cobordisms and string theory.
The concept of currying was introduced by
Gottlob Frege
Friedrich Ludwig Gottlob Frege (; ; 8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician. He was a mathematics professor at the University of Jena, and is understood by many to be the father of analytic philos ...
,
developed by
Moses Schönfinkel
Moses Ilyich Schönfinkel (; 29 September 1888 – ) was a logician and mathematician, known for the invention of combinatory logic.
Life
Moses Schönfinkel was born on in Ekaterinoslav, Russian Empire (now Dnipro, Ukraine). He was born to a J ...
,
[Originally published as
Republished as ]
and further developed by
Haskell Curry
Haskell Brooks Curry ( ; September 12, 1900 – September 1, 1982) was an American mathematician, logician and computer scientist. Curry is best known for his work in combinatory logic, whose initial concept is based on a paper by Moses Schönfin ...
.
Uncurrying is the
dual
Dual or Duals may refer to:
Paired/two things
* Dual (mathematics), a notion of paired concepts that mirror one another
** Dual (category theory), a formalization of mathematical duality
*** see more cases in :Duality theories
* Dual number, a nu ...
transformation to currying, and can be seen as a form of
defunctionalization
In programming languages, defunctionalization is 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 pa ...
. It takes a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-orie ...
whose return value is another function
, and yields a new function
that takes as parameters the arguments for both
and
, and returns, as a result, the application of
and subsequently,
, to those arguments. The process can be iterated.
Motivation
Currying provides a way for working with functions that take multiple arguments, and using them in frameworks where functions might take only one argument. For example, some
analytical techniques can only be applied to
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-orie ...
s with a single argument. Practical functions frequently take more arguments than this.
Frege
Friedrich Ludwig Gottlob Frege (; ; 8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician. He was a mathematics professor at the University of Jena, and is understood by many to be the father of analytic philos ...
showed that it was sufficient to provide solutions for the single argument case, as it was possible to transform a function with multiple arguments into a chain of single-argument functions instead. This transformation is the process now known as currying. All "ordinary" functions that might typically be encountered in
mathematical analysis
Analysis is the branch of mathematics dealing with continuous functions, limit (mathematics), limits, and related theories, such as Derivative, differentiation, Integral, integration, measure (mathematics), measure, infinite sequences, series ( ...
or in
computer programming
Computer programming or coding is the composition of sequences of instructions, called computer program, programs, that computers can follow to perform tasks. It involves designing and implementing algorithms, step-by-step specifications of proc ...
can be curried. However, there are categories in which currying is not possible; the most general categories which allow currying are the
closed monoidal categories.
Some
programming language
A programming language is a system of notation for writing computer programs.
Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...
s almost always use curried functions to achieve multiple arguments; notable examples are
ML and
Haskell
Haskell () is a general-purpose, statically typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research, and industrial applications, Haskell pioneered several programming language ...
, where in both cases all functions have exactly one argument. This property is inherited from
lambda calculus
In mathematical logic, the lambda calculus (also written as ''λ''-calculus) is a formal system for expressing computability, computation based on function Abstraction (computer science), abstraction and function application, application using var ...
, where multi-argument functions are usually represented in curried form.
Currying is related to, but not the same as
partial application
Partial may refer to:
Mathematics
*Partial derivative, derivative with respect to one of several variables of a function, with the other variables held constant
** ∂, a symbol that can denote a partial derivative, sometimes pronounced "partial ...
.
In practice, the programming technique of
closures can be used to perform partial application and a kind of currying, by hiding arguments in an environment that travels with the curried function.
History
The "Curry" in "Currying" is a reference to logician
Haskell Curry
Haskell Brooks Curry ( ; September 12, 1900 – September 1, 1982) was an American mathematician, logician and computer scientist. Curry is best known for his work in combinatory logic, whose initial concept is based on a paper by Moses Schönfin ...
, who used the concept extensively, but
Moses Schönfinkel
Moses Ilyich Schönfinkel (; 29 September 1888 – ) was a logician and mathematician, known for the invention of combinatory logic.
Life
Moses Schönfinkel was born on in Ekaterinoslav, Russian Empire (now Dnipro, Ukraine). He was born to a J ...
had the idea six years before Curry.
The alternative name "Schönfinkelisation" has been proposed. In the mathematical context, the principle can be traced back to work in 1893 by
Frege
Friedrich Ludwig Gottlob Frege (; ; 8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician. He was a mathematics professor at the University of Jena, and is understood by many to be the father of analytic philos ...
.
The originator of the word "currying" is not clear. David Turner says the word was coined by Christopher Strachey
Christopher S. Strachey (; 16 November 1916 – 18 May 1975) was a British computer scientist. He was one of the founders of denotational semantics, and a pioneer in programming language design and computer time-sharing.F. J. Corbató, et al., T ...
in his 1967 lecture notes Fundamental Concepts in Programming Languages
''Fundamental Concepts in Programming Languages'' were an influential set of lecture notes written by Christopher Strachey for the International Summer School in Computer Programming at Copenhagen in August, 1967. It introduced much programming ...
, but that source introduces the concept as "a device originated by Schönfinkel", and the term "currying" is not used, while Curry is mentioned later in the context of higher-order functions.[ ]John C. Reynolds
John Charles Reynolds (June 1, 1935 – April 28, 2013) was an American computer scientist.
Education and affiliations
John Reynolds studied at Purdue University and then earned a Doctor of Philosophy (Ph.D.) in theoretical physics from Harvard U ...
defined "currying" in a 1972 paper, but did not claim to have coined the term.[
]
Definition
Currying is most easily understood by starting with an informal definition, which can then be molded to fit many different domains. First, there is some notation to be established. The notation denotes all functions from to . If is such a function, we write . Let denote the ordered pair
In mathematics, an ordered pair, denoted (''a'', ''b''), is a pair of objects in which their order is significant. The ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a''), unless ''a'' = ''b''. In contrast, the '' unord ...
s of the elements of and respectively, that is, the Cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets and , denoted , is the set of all ordered pairs where is an element of and is an element of . In terms of set-builder notation, that is
A\times B = \.
A table c ...
of and . Here, and may be sets, or they may be types, or they may be other kinds of objects, as explored below.
Given a function
:,
currying constructs a new function
:.
That is, takes an argument of type and returns a function of type . It is defined by
:
for of type and of type . We then also write
:
Uncurrying is the reverse transformation, and is most easily understood in terms of its right adjoint, the function
Set theory
In set theory
Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory – as a branch of mathema ...
, the notation is used to denote the set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of functions from the set to the set . Currying is the natural bijection between the set of functions from to , and the set of functions from to the set of functions from to . In symbols:
:
Indeed, it is this natural bijection that justifies the exponential notation
Scientific notation is a way of expressing numbers that are too large or too small to be conveniently written in decimal form, since to do so would require writing out an inconveniently long string of digits. It may be referred to as scientif ...
for the set of functions. As is the case in all instances of currying, the formula above describes an adjoint pair of functors: for every fixed set , the functor is left adjoint to the functor .
In the category of sets
In the mathematical field of category theory, the category of sets, denoted by Set, is the category whose objects are sets. The arrows or morphisms between sets ''A'' and ''B'' are the functions from ''A'' to ''B'', and the composition of mor ...
, the object
Object may refer to:
General meanings
* Object (philosophy), a thing, being, or concept
** Object (abstract), an object which does not exist at any particular time or place
** Physical object, an identifiable collection of matter
* Goal, an a ...
is called the exponential object
In mathematics, specifically in category theory, an exponential object or map object is the category theory, categorical generalization of a function space in set theory. Category (mathematics), Categories with all Product (category theory), fini ...
.
Function spaces
In the theory of function space
In mathematics, a function space is a set of functions between two fixed sets. Often, the domain and/or codomain will have additional structure which is inherited by the function space. For example, the set of functions from any set into a ve ...
s, such as in functional analysis
Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure (for example, Inner product space#Definition, inner product, Norm (mathematics ...
or homotopy theory
In mathematics, homotopy theory is a systematic study of situations in which Map (mathematics), maps can come with homotopy, homotopies between them. It originated as a topic in algebraic topology, but nowadays is learned as an independent discipli ...
, one is commonly interested in continuous function
In mathematics, a continuous function is a function such that a small variation of the argument induces a small variation of the value of the function. This implies there are no abrupt changes in value, known as '' discontinuities''. More preci ...
s between topological space
In mathematics, a topological space is, roughly speaking, a Geometry, geometrical space in which Closeness (mathematics), closeness is defined but cannot necessarily be measured by a numeric Distance (mathematics), distance. More specifically, a to ...
s. One writes (the Hom functor
In mathematics, specifically in category theory, hom-sets (i.e. sets of morphisms between object (category theory), objects) give rise to important functors to the category of sets. These functors are called hom-functors and have numerous applicati ...
) for the set of ''all'' functions from to , and uses the notation to denote the subset of continuous functions. Here, is the bijection
In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equival ...
:
while uncurrying is the inverse map. If the set of continuous functions from to is given the compact-open topology
In mathematics, the compact-open topology is a topology defined on the set of continuous maps between two topological spaces. The compact-open topology is one of the commonly used topologies on function spaces, and is applied in homotopy theory ...
, and if the space is locally compact Hausdorff
In topology and related branches of mathematics, a topological space is called locally compact if, roughly speaking, each small portion of the space looks like a small portion of a compact space. More precisely, it is a topological space in which e ...
, then
:
is a homeomorphism
In mathematics and more specifically in topology, a homeomorphism ( from Greek roots meaning "similar shape", named by Henri Poincaré), also called topological isomorphism, or bicontinuous function, is a bijective and continuous function ...
. This is also the case when , and are compactly generated In mathematics, compactly generated can refer to:
* Compactly generated group, a topological group which is algebraically generated by one of its compact subsets
*Compactly generated space
In topology, a topological space X is called a compactly ge ...
, although there are more cases.
One useful corollary is that a function is continuous if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
its curried form is continuous. Another important result is that the application map, usually called "evaluation" in this context, is continuous (note that eval
In some programming languages, eval , short for evaluate, is a function which evaluates a string as though it were an expression in the language, and returns a result; in others, it executes multiple lines of code as though they had been incl ...
is a strictly different concept in computer science.) That is,
is continuous when is compact-open and locally compact Hausdorff. These two results are central for establishing the continuity of homotopy
In topology, two continuous functions from one topological space to another are called homotopic (from and ) if one can be "continuously deformed" into the other, such a deformation being called a homotopy ( ; ) between the two functions. ...
, i.e. when is the unit interval , so that can be thought of as either a homotopy of two functions from to , or, equivalently, a single (continuous) path in .
Algebraic topology
In algebraic topology
Algebraic topology is a branch of mathematics that uses tools from abstract algebra to study topological spaces. The basic goal is to find algebraic invariant (mathematics), invariants that classification theorem, classify topological spaces up t ...
, currying serves as an example of Eckmann–Hilton duality
In the mathematical disciplines of algebraic topology and homotopy theory, Eckmann–Hilton duality in its most basic form, consists of taking a given diagram for a particular concept and reversing the direction of all arrows, much as in cate ...
, and, as such, plays an important role in a variety of different settings. For example, loop space
In topology, a branch of mathematics, the loop space Ω''X'' of a pointed topological space ''X'' is the space of (based) loops in ''X'', i.e. continuous pointed maps from the pointed circle ''S''1 to ''X'', equipped with the compact-open topolog ...
is adjoint to reduced suspension
In topology, a branch of mathematics, the suspension of a topological space ''X'' is intuitively obtained by stretching ''X'' into a cylinder and then collapsing both end faces to points. One views ''X'' as "suspended" between these end points. The ...
s; this is commonly written as
: