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
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-oriente ...
that takes multiple
arguments
An argument is a statement or group of statements called premises intended to determine the degree of truth or acceptability of another statement called conclusion. Arguments can be studied from three main perspectives: the logical, the dialectic ...
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
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 ma ...
. 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
In computer science, partial application (or partial function application) refers to the process of fixing a number of arguments to a function, producing another function of smaller arity. Given a function f \colon (X \times Y \times Z) \to N , ...
.
Currying is useful in both practical and theoretical settings. In
functional programming language
In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that m ...
s, 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 (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 circumsc ...
, 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 relati ...
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 phil ...
,
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 phil ...
, ''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
Moses Ilyich Schönfinkel (russian: Моисей Исаевич Шейнфинкель, translit=Moisei Isai'evich Sheinfinkel; 29 September 1888 – 1942) was a logician and mathematician, known for the invention of combinatory logic.
Life
Mose ...
'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
Jean Louis Maxime van Heijenoort (; July 23, 1912 – March 29, 1986) was a historian of mathematical logic. He was also a personal secretary to Leon Trotsky from 1932 to 1939, and an American Trotskyist until 1947.
Life
Van Heijenoort was born ...
(1967), ''A Source Book in Mathematical Logic, 1879–1931''. Harvard University Press, pp. 355–66. developed by
Moses Schönfinkel
Moses Ilyich Schönfinkel (russian: Моисей Исаевич Шейнфинкель, translit=Moisei Isai'evich Sheinfinkel; 29 September 1888 – 1942) was a logician and mathematician, known for the invention of combinatory logic.
Life
Mose ...
,
[ (Reprinted lecture notes from 1967.)]
and further developed by Haskell Curry
Haskell Brooks Curry (; September 12, 1900 – September 1, 1982) 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 ...
.
Uncurrying is the dual 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 p ...
. 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-oriente ...
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 Analytical technique is a method used to determine a chemical or physical property of a chemical substance, chemical element, or mixture. There is a wide variety of techniques used for analysis, from simple weighing to advanced techniques using high ...
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-oriente ...
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 ph ...
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 (m ...
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 ana ...
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
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 has pioneered a number of programming lan ...
, 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 ...
, where multi-argument functions are usually represented in curried form.
Currying is related to, but not the same as partial application
In computer science, partial application (or partial function application) refers to the process of fixing a number of arguments to a function, producing another function of smaller arity. Given a function f \colon (X \times Y \times Z) \to N , ...
. 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 real ...
() 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
Haskell Brooks Curry (; September 12, 1900 – September 1, 1982) 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 ...
, who used the concept extensively, but Moses Schönfinkel
Moses Ilyich Schönfinkel (russian: Моисей Исаевич Шейнфинкель, translit=Moisei Isai'evich Sheinfinkel; 29 September 1888 – 1942) was a logician and mathematician, known for the invention of combinatory logic.
Life
Mose ...
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 ph ...
.[
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., ...
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\ti ...
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 conce ...
, 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
In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets ''A'' and ''B'' are the total functions from ''A'' to ''B'', and the composition of m ...
, 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
In mathematics, specifically in category theory, an exponential object or map object is the categorical generalization of a function space in set theory. Categories with all finite products and exponential objects are called cartesian closed c ...
.
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 space#Definition, inner product, Norm (mathematics)#Defini ...
or homotopy theory
In mathematics, homotopy theory is a systematic study of situations in which maps can come with homotopies between them. It originated as a topic in algebraic topology but nowadays is studied as an independent discipline. Besides algebraic topolog ...
, 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 value ...
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 points ...
s. One writes (the Hom functor
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 ...
) 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 s ...
:
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 ...
, 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 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 isomorphi ...
. 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 compactly generated space is a topological s ...
,[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 bicondi ...
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 the English 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 b ...
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 deforma ...
, 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 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 topology ...
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
: