HOME

TheInfoList



OR:

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 f that takes three arguments creates a nested unary function g, so that the code :\textx=f(a,b,c) gives x the same value as the code : \begin \texth = g(a) \\ \texti = h(b) \\ \textx = i(c), \end or called in sequence, :\textx = g(a)(b)(c). In a more mathematical language, a function that takes two arguments, one from X and one from Y, and produces outputs in Z, by currying is translated into a function that takes a single argument from X and produces as outputs ''functions'' from Y to Z. 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 f whose return value is another function g, and yields a new function f' that takes as parameters the arguments for both f and g, and returns, as a result, the application of f and subsequently, g, 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 f:\mathbb\times\mathbb\to\mathbb 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 ...
(\mathbb) arguments and outputs real numbers, and it is defined by f(x,y)=x+y^2. Currying translates this into a function h which takes a single real argument and outputs functions from \mathbb to \mathbb. In symbols, h:\mathbb\to\mathbb^\mathbb, where \mathbb^\mathbbdenotes the set of all functions that take a single real argument and produce real outputs. For every real number x, define the function h_x : \mathbb\to\mathbb by h_x(y)=x+y^2, and then define the function h:\mathbb\to\mathbb^\mathbb by h(x)=h_x. So for instance, h(2) is the function that sends its real argument y to the output 2+y^2, or h(2)(y)=h_2(y)=2+y^2. We see that in general :h(x)(y)=x+y^2=f(x,y) so that the original function f and its currying h convey exactly the same information. In this situation, we also write :\text(f) = h. This also works for functions with more than two arguments. If f were a function of three arguments f(x,y,z), its currying h would have the property :f(x,y,z)=h(x)(y)(z).


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 X \to Y denotes all functions from X to Y. If f is such a function, we write f \colon X \to Y . Let X \times Y 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 X and Y 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 X and Y. Here, X and Y may be sets, or they may be types, or they may be other kinds of objects, as explored below. Given a function :f \colon (X \times Y) \to Z , currying constructs a new function :h \colon X \to (Y \to Z) . That is, h takes an argument from X and returns a function that maps Y to Z. It is defined by :h(x)(y)=f(x,y) for x from X and y from Y. We then also write :\text(f)=h. Uncurrying is the reverse transformation, and is most easily understood in terms of its right adjoint, the function \operatorname.


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 Y^X 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 X to the set Y. Currying is the natural bijection between the set A^ of functions from B\times C to A, and the set (A^C)^B of functions from B to the set of functions from C to A. In symbols: :A^\cong (A^C)^B 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 C, the functor B\mapsto B\times C is left adjoint to the functor A \mapsto A^C. 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 ...
Y^X 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 \text(X,Y) (the Hom functor) for the set of ''all'' functions from X to Y, and uses the notation Y^X to denote the subset of continuous functions. Here, \text 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 ...
:\text:\text(X\times Y, Z) \to \text(X, \text(Y,Z)) , while uncurrying is the inverse map. If the set Y^X of continuous functions from X to Y is given the compact-open topology, and if the space Y 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 :\text : Z^\to (Z^Y)^X 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 X, Y and Y^X 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, \begin &&\text:Y^X \times X \to Y \\ && (f,x) \mapsto f(x) \end is continuous when Y^X is compact-open and Y 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 X is the unit interval I, so that Z^ \cong (Z^Y)^I can the thought of as either a homotopy of two functions from Y to Z, or, equivalently, a single (continuous) path in Z^Y.


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 : Sigma X,Z\approxeq , \Omega Z/math> where ,B/math> is the set of homotopy classes of maps A \rightarrow B, and \Sigma A is the suspension of ''A'', and \Omega A is the
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 ...
of ''A''. In essence, the suspension \Sigma X can be seen as the cartesian product of X with the unit interval, modulo an equivalence relation to turn the interval into a loop. The curried form then maps the space X to the space of functions from loops into Z, that is, from X into \Omega Z. Then \text is the adjoint functor that maps suspensions to loop spaces, and uncurrying is the dual. The duality between the mapping cone and the mapping fiber ( cofibration and fibration) can be understood as a form of currying, which in turn leads to the duality of the long exact and coexact
Puppe sequence In mathematics, the Puppe sequence is a construction of homotopy theory, so named after Dieter Puppe. It comes in two forms: a long exact sequence, built from the mapping fibre (a fibration), and a long coexact sequence, built from the mapping co ...
s. In homological algebra, the relationship between currying and uncurrying is known as tensor-hom adjunction. Here, an interesting twist arises: the Hom functor and the
tensor product In mathematics, the tensor product V \otimes W of two vector spaces and (over the same field) is a vector space to which is associated a bilinear map V\times W \to V\otimes W that maps a pair (v,w),\ v\in V, w\in W to an element of V \otime ...
functor might not lift to an exact sequence; this leads to the definition of the Ext functor and the
Tor functor In mathematics, the Tor functors are the derived functors of the tensor product of modules over a ring. Along with the Ext functor, Tor is one of the central concepts of homological algebra, in which ideas from algebraic topology are used to co ...
.


Domain theory

In
order theory Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...
, that is, the theory of lattices of
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
s, \text is a
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 ...
when the lattice is given the Scott topology. Scott-continuous functions were first investigated in the attempt to provide a semantics for
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 ...
(as ordinary set theory is inadequate to do this). More generally, Scott-continuous functions are now studied in domain theory, which encompasses the study of denotational semantics of computer algorithms. Note that the Scott topology is quite different than many common topologies one might encounter in the
category of topological spaces In mathematics, the category of topological spaces, often denoted Top, is the category whose objects are topological spaces and whose morphisms are continuous maps. This is a category because the composition of two continuous maps is again cont ...
; the Scott topology is typically finer, and is not sober. The notion of continuity makes its appearance in homotopy type theory, where, roughly speaking, two computer programs can be considered to be homotopic, i.e. compute the same results, if they can be "continuously" refactored from one to the other.


Lambda calculi

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 ...
, currying provides a way to study functions with multiple arguments in very simple theoretical models, such as the
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 ...
, in which functions only take a single argument. Consider a function f(x,y) taking two arguments, and having the type (X \times Y)\to Z, which should be understood to mean that ''x'' must have the type X, ''y'' must have the type Y, and the function itself returns the type Z. The curried form of ''f'' is defined as :\text(f) = \lambda x.(\lambda y.(f(x,y))) where \lambda is the abstractor of lambda calculus. Since curry takes, as input, functions with the type (X\times Y)\to Z, one concludes that the type of curry itself is :\text:((X \times Y)\to Z) \to (X \to (Y \to Z)) The → operator is often considered right-associative, so the curried function type X \to (Y \to Z) is often written as X \to Y \to Z. Conversely,
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. In this sense, function application can be thought of as the opposite of function abst ...
is considered to be left-associative, so that f(x, y) is equivalent to :((\text(f) \; x) \;y) = \text(f) \; x \;y. That is, the parenthesis are not required to disambiguate the order of the application. Curried functions may be used in any
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 ...
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.


Type theory

In
type theory In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a founda ...
, the general idea of a
type system In computer programming, a type system is a logical system comprising a set of rules that assigns a property called a type to every "term" (a word, phrase, or other set of symbols). Usually the terms are various constructs of a computer progra ...
in computer science is formalized into a specific algebra of types. For example, when writing f \colon X \to Y , the intent is that X and Y are types, while the arrow \to is a type constructor, specifically, the function type or arrow type. Similarly, the Cartesian product X \times Y of types is constructed by the product type constructor \times. The type-theoretical approach is expressed in programming languages such as ML and the languages derived from and inspired by it: CaML, Haskell and F#. The type-theoretical approach provides a natural complement to the language of
category theory Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, ca ...
, as discussed below. This is because categories, and specifically, monoidal categories, have an internal language, with simply-typed lambda calculus being the most prominent example of such a language. It is important in this context, because it can be built from a single type constructor, the arrow type. Currying then endows the language with a natural product type. The correspondence between objects in categories and types then allows programming languages to be re-interpreted as logics (via
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 ...
), and as other types of mathematical systems, as explored further, below.


Logic

Under 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 ...
, the existence of currying and uncurrying is equivalent to the logical theorem (A \land B) \to C \Leftrightarrow A \to (B \to C), as
tuple In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
s ( product type) corresponds to conjunction in logic, and function type corresponds to implication. The exponential object Q^P in the category of Heyting algebras is normally written as material implication P\to Q. Distributive Heyting algebras are
Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
s, and the exponential object has the explicit form \neg P \lor Q, thus making it clear that the exponential object really is material implication.


Category theory

The above notions of currying and uncurrying find their most general, abstract statement in
category theory Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, ca ...
. Currying is a
universal property In mathematics, more specifically in category theory, a universal property is a property that characterizes up to an isomorphism the result of some constructions. Thus, universal properties can be used for defining some objects independently fr ...
of an exponential object, and gives rise to an adjunction in
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 mat ...
. That is, there is a
natural Nature, in the broadest sense, is the physical world or universe. "Nature" can refer to the phenomena of the physical world, and also to life in general. The study of nature is a large, if not the only, part of science. Although humans ar ...
isomorphism In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...
between the
morphisms In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms ...
from a binary product f \colon (X \times Y) \to Z and the morphisms to an exponential object g \colon X \to Z^Y . This generalizes to a broader result in
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 ...
: Currying is the statement that the
tensor product In mathematics, the tensor product V \otimes W of two vector spaces and (over the same field) is a vector space to which is associated a bilinear map V\times W \to V\otimes W that maps a pair (v,w),\ v\in V, w\in W to an element of V \otime ...
and the
internal Hom 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 a ...
are adjoint functors; that is, for every object B there is a natural isomorphism: : \mathrm(A\otimes B, C) \cong \mathrm(A, B\Rightarrow C) . Here, ''Hom'' denotes the (external) Hom-functor of all morphisms in the category, while B\Rightarrow C denotes the internal hom functor in the closed monoidal category. For the category of sets, the two are the same. When the product is the cartesian product, then the internal hom B\Rightarrow C becomes the exponential object C^B. Currying can break down in one of two ways. One is if a category is not
closed Closed may refer to: Mathematics * Closure (mathematics), a set, along with operations, for which applying those operations on members always results in a member of the set * Closed set, a set which contains all its limit points * Closed interval, ...
, and thus lacks an internal hom functor (possibly because there is more than one choice for such a functor). Another way is if it is not monoidal, and thus lacks a product (that is, lacks a way of writing down pairs of objects). Categories that do have both products and internal homs are exactly the closed monoidal categories. The setting of cartesian closed categories is sufficient for the discussion of classical logic; the more general setting of closed monoidal categories is suitable for
quantum computation Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
. The difference between these two is that the product for cartesian categories (such as the category of sets, complete partial orders or Heyting algebras) is just 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 ...
; it is interpreted as an
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 ...
of items (or a list). Simply typed lambda calculus is the internal language of cartesian closed categories; and it is for this reason that pairs and lists are the primary types in the
type theory In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a founda ...
of LISP,
Scheme A scheme is a systematic plan for the implementation of a certain idea. Scheme or schemer may refer to: Arts and entertainment * ''The Scheme'' (TV series), a BBC Scotland documentary series * The Scheme (band), an English pop band * ''The Schem ...
and many functional programming languages. By contrast, the product for monoidal categories (such as
Hilbert space In mathematics, Hilbert spaces (named after David Hilbert) allow generalizing the methods of linear algebra and calculus from (finite-dimensional) Euclidean vector spaces to spaces that may be infinite-dimensional. Hilbert spaces arise natural ...
and the
vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
s of
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 ...
) is the
tensor product In mathematics, the tensor product V \otimes W of two vector spaces and (over the same field) is a vector space to which is associated a bilinear map V\times W \to V\otimes W that maps a pair (v,w),\ v\in V, w\in W to an element of V \otime ...
. The internal language of such categories is
linear logic Linear logic is a substructural logic proposed by Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter. Although the logic has also ...
, a form of
quantum logic In the mathematical study of logic and the physical analysis of quantum foundations, quantum logic is a set of rules for manipulation of propositions inspired by the structure of quantum theory. The field takes as its starting point an observ ...
; the corresponding
type system In computer programming, a type system is a logical system comprising a set of rules that assigns a property called a type to every "term" (a word, phrase, or other set of symbols). Usually the terms are various constructs of a computer progra ...
is the linear type system. Such categories are suitable for describing
entangled quantum states Quantum entanglement is the phenomenon that occurs when a group of particles are generated, interact, or share spatial proximity in a way such that the quantum state of each particle of the group cannot be described independently of the state of ...
, and, more generally, allow 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 ...
to
quantum mechanics Quantum mechanics is a fundamental theory in physics that provides a description of the physical properties of nature at the scale of atoms and subatomic particles. It is the foundation of all quantum physics including quantum chemistry, ...
, to cobordisms 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 ...
, and to
string theory In physics, string theory is a theoretical framework in which the point-like particles of particle physics are replaced by one-dimensional objects called strings. String theory describes how these strings propagate through space and intera ...
.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.
The linear type system, and
linear logic Linear logic is a substructural logic proposed by Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter. Although the logic has also ...
are useful for describing
synchronization primitive In computer science, synchronization refers to one of two distinct but related concepts: synchronization of processes, and synchronization of data. ''Process synchronization'' refers to the idea that multiple processes are to join up or hands ...
s, such as mutual exclusion locks, and the operation of vending machines.


Contrast with partial function application

Currying and partial function application are often conflated. 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 Arity () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematics. ...
is greater than two. Given a function of type f \colon (X \times Y \times Z) \to N , currying produces \text(f) \colon X \to (Y \to (Z \to N)) . That is, while an evaluation of the first function might be represented as f(1, 2, 3), evaluation of the curried function would be represented as f_\text(1)(2)(3), applying each argument in turn to a single-argument function returned by the previous invocation. Note that after calling f_\text(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 f above, we might fix (or 'bind') the first argument, producing a function of type \text(f) \colon (Y \times Z) \to N. Evaluation of this function might be represented as f_\text(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
argument 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 dialecti ...
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. Partial application can be seen as evaluating a curried function at a fixed point, e.g. given f \colon (X \times Y \times Z) \to N and a \in X then \text(\text(f)_a)(y)(z) = \text(f)(a)(y)(z) or simply \text(f)_a = \text_1(f)(a) where \text_1 curries f's first parameter. Thus, partial application is reduced to a curried function at a fixed point. Further, a curried function at a fixed point is (trivially), a partial application. For further evidence, note that, given any function f(x,y), a function g(y,x) may be defined such that g(y,x) = f(x,y). Thus, any partial application may be reduced to a single curry operation. As such, curry is more suitably defined as an operation which, in many theoretical cases, is often applied recursively, but which is theoretically indistinguishable (when considered as an operation) from a partial application. So, a partial application can be defined as the objective result of a single application of the curry operator on some ordering of the inputs of some function.


See also

* Tensor-hom adjunction * Lazy evaluation * Closure (computer science) * ' theorem * Closed monoidal category


Notes


References

* *


External links


Currying Schonfinkelling
at the Portland Pattern Repository
Currying != Generalized Partial Application!
- post at Lambda-the-Ultimate.org {{Design Patterns Patterns Higher-order functions Functional programming Lambda calculus Articles with example Java code