In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, currying is the technique of translating the evaluation of a
function that takes multiple
arguments into evaluating a sequence of functions, each with a single argument. For example, currying a function
that takes three arguments creates a nested unary function
, so that the code
:
gives
the same value as the code
:
or called in sequence,
:
In a more mathematical language, a function that takes two arguments, one from
and one from
, and produces outputs in
by currying is translated into a function that takes a single argument from
and produces as outputs ''functions'' from
to
This is a natural one-to-one correspondence between these two types of functions, so that 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 ...
s together with functions between them form a
Cartesian closed category. The currying of a function with more than two arguments can then be defined by induction. Currying is related to, but not the same as,
partial application.
Currying is useful in both practical and theoretical settings. In
functional programming languages, and many others, it provides a way of automatically managing how arguments are passed to functions and exceptions. In
theoretical computer science
computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumscribe the ...
, 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
In mathematics, especially in category theory, a closed monoidal category (or a ''monoidal closed category'') is a category that is both a monoidal category and a closed category in such a way that the structures are compatible.
A classic example ...
, which underpins a vast generalization of the
Curry–Howard correspondence
In programming language theory and proof theory, the Curry–Howard correspondence (also known as the Curry–Howard isomorphism or equivalence, or the proofs-as-programs and propositions- or formulae-as-types interpretation) is the direct rela ...
of proofs and programs to a correspondence with many other structures, including quantum mechanics, cobordisms and string theory.
It 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 p ...
,
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 p ...
, ''Grundgesetze der Arithmetik'' I, Jena: Verlag Hermann Pohle, 1893, §36.Willard Van Orman Quine
Willard Van Orman Quine (; known to his friends as "Van"; June 25, 1908 – December 25, 2000) was an American philosopher and logician in the analytic tradition, recognized as "one of the most influential philosophers of the twentieth century" ...
, introduction to Moses Schönfinkel's "Bausteine der mathematischen Logik", pp. 355–357, esp. 355. Translated by Stefan Bauer-Mengelberg as "On the building blocks of mathematical logic" in Jean van Heijenoort (1967), ''A Source Book in Mathematical Logic, 1879–1931''. Harvard University Press, pp. 355–66. developed by
Moses Schönfinkel,
[ (Reprinted lecture notes from 1967.)]
and further developed by Haskell Curry.
Uncurrying is the dual transformation to currying, and can be seen as a form of defunctionalization. It takes a function 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 functions 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 p ...
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, limits, and related theories, such as differentiation, integration, measure, infinite sequences, series, and analytic functions.
These theories are usually studied ...
or in computer programming
Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as anal ...
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
In mathematics, especially in category theory, a closed monoidal category (or a ''monoidal closed category'') is a category that is both a monoidal category and a closed category in such a way that the structures are compatible.
A classic example ...
.
Some programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
s 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. This property is inherited from lambda calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation th ...
, where multi-argument functions are usually represented in curried form.
Currying is related to, but not the same as partial application. 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.
Illustration
Suppose we have a function which takes two real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
() arguments and outputs real numbers, and it is defined by . Currying translates this into a function which takes a single real argument and outputs functions from to . In symbols, , where denotes the set of all functions that take a single real argument and produce real outputs. For every real number , define the function by , and then define the function by . So for instance, is the function that sends its real argument to the output , or . We see that in general
:
so that the original function and its currying convey exactly the same information. In this situation, we also write
:
This also works for functions with more than two arguments. If were a function of three arguments , its currying would have the property
:
History
The "Curry" in "Currying" is a reference to logician Haskell Curry, who used the concept extensively, but Moses Schönfinkel had the idea 6 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 p ...
.[
The originator of the word "currying" is not clear. David Turner says the word was coined by Christopher Strachey 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 l ...
, but although the concept is mentioned, the word "currying" does not appear in the notes.[ ]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 (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
s of the elements of and respectively, that is, the Cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\t ...
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 from and returns a function that maps to . It is defined by
:
for from and from . 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 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 mathematics, is mostly concern ...
, 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 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, 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 ...
is called the exponential object.
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 vect ...
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 (e.g. inner product, norm, topology, etc.) and the linear functions defi ...
or homotopy theory, one is commonly interested in continuous function
In mathematics, a continuous function is a function such that a continuous variation (that is a change without jump) of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in val ...
s between topological space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called poin ...
s. One writes (the Hom functor) 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, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
:
while uncurrying is the inverse map. If the set of continuous functions from to is given the compact-open topology, 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 ...
, then
:
is a homeomorphism
In the mathematical field of topology, a homeomorphism, topological isomorphism, or bicontinuous function is a bijective and continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isom ...
. This is also the case when , and are compactly generated,[J.P. May, ]
A Concise Course in Algebraic Topology
', (1999) Chicago Lectures in Mathematics 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" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bic ...
its curried form is continuous. Another important result is that the application map, usually called "evaluation" in this context, is continuous (note that eval is a strictly different concept in computer science.) That is,
is continuous when is compact-open and locally compact Hausdorff.[Joseph J. Rotman, ''An Introduction to Algebraic Topology'' (1988) Springer-Verlag ''(See Chapter 11 for proof.)''] These two results are central for establishing the continuity of homotopy
In topology, a branch of mathematics, two continuous functions from one topological space to another are called homotopic (from grc, ὁμός "same, similar" and "place") if one can be "continuously deformed" into the other, such a deform ...
, i.e. when is the unit interval , so that can the 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 invariants that classify topological spaces up to homeomorphism, though usually most classify ...
, 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 cat ...
, 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 topol ...
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. T ...
s; this is commonly written as
: