Currying
Learn more about Currying
- This article is about the computing technique. For the cooking technique see Curry.
In computer science and linguistics (semantics), currying or Schönfinkelisation <ref>I. Heim and A. Kratzer (1998). Semantics in Generative Grammar. Blackwell.</ref> is the technique of transforming a function that takes multiple arguments into a function that takes a single argument (the first of the arguments to the original function) and returns a new function that takes the remainder of the arguments and returns the result. The technique was named by Christopher Strachey after logician Haskell Curry, though it was invented by Moses Schönfinkel and Gottlob Frege.
If function f has the typing f : (X × Y) → Z, and g is f after currying, then g has the typing g : X → (Y → Z) . Uncurrying is the reverse transformation.
Intuitively, currying says "if you fix some arguments, you get a function of the remaining arguments". For example, if function div stands for the curried form of the division operation /, then 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.
In theoretical computer science, currying provides a way to study functions with multiple arguments in very simple theoretical models such as the lambda calculus in which functions only take a single argument. In category theory, currying is a morphism from an object to an exponential object.
The practical motivation for currying is that very often the functions you get by supplying some but not all of the arguments to a curried function are useful; for example, many languages have a function or operator similar to plus_one. Currying makes it easy to define these functions.
Some programming languages are based on currying, notably ML and Haskell in which functions only ever take a single argument, and multiple-arguments functions are syntactic sugar for nested functions. Any language that supports functions as first-class objects, including Lisp, Scheme, Eiffel, Perl, Ruby, Python, R, S, Groovy and JavaScript can be used to write curried functions. As of version 2.5, Python includes a standard library module implementing partial function application, which is more generic than the previous approach based on the lambda operator.
Contents |
[edit] Examples
Suppose that plus is a function taking two arguments x and y and returning x + y. In the ML programming language we would define it as follows:
plus = fn(x, y) => x + y
and plus(1, 2) returns 3 as we expect.
The curried version of plus takes a single argument x and returns a new function which takes a single argument y and returns x + y. In ML we would define it as follows:
curried_plus = fn(x) => fn(y) => x + y
and now when we call curried_plus(1) we get a new function that adds 1 to its argument:
plus_one = curried_plus(1)
and now plus_one(2) returns 3 and plus_one(7) returns 8.
When declaring functions in the strictly-typed OCaml programming language, the type returned by a function shows the Curried form of the function. Typing the function into the OCaml interpreter displays the type immediately:
# let plus x y = x + y ;; val plus : int -> int -> int = <fun>
Likewise in Haskell, function type signatures show the currying-based structure of functions (note: "\ ->" is Haskell's syntax for anonymous functions. \ has been chosen because it looks like a mathematical λ (lambda), it is followed by a list of space-separated arguments, and the -> separates the arguments list and the function body)
Prelude> let plus = \x y -> x + y Prelude> :type plus plus :: Integer -> Integer -> Integer Prelude> plus 3 5 8
and currying functions is trivial
Prelude> let plus5 = plus 5 Prelude> :type plus5 plus5 :: Integer -> Integer Prelude> plus5 3 8
In fact, the haskell definition \x y -> x + y is merely syntactic sugar for \x -> \y -> x + y, which has exactly the same type signature:
Prelude> let nested_plus = \x -> \y -> x + y Prelude> :type nested_plus nested_plus :: Integer -> Integer -> Integer
[edit] C++
Currying may be achieved in C++ using the Standard Template Library function object adapters (binder1st and binder2nd), and more generically using the Boost bind mechanism.
[edit] Eiffel
Eiffel has direct support for lambda expressions and hence currying through "inline agents". If f is a function with two arguments, of signature (X × Y) → Z then its curried version is obtained by simply writing
g (x: X): FUNCTION [ANY, TUPLE [Y], Z]
do
Result := agent (closed_x: X; y: Y): Z
do
Result := f (closed_x, y)
end (x, ?)
end
where FUNCTION [ANY, TUPLE [Y], Z] denotes the type Y → Z (agents taking as argument a tuple with a single argument of type Y and returning a result of type Z), which is indeed the type of the agent expression used on the next-to-last line to define the "Result" of g.
[edit] Scheme
This is a simple general currying function written in Scheme:
(define (curry f . x)
(lambda (y)
(apply f (append x (list y)))))
This is an example of a curried function:
(define add5 (curry + 5)) > (add5 37) 42
[edit] Python
As of Python 2.5 (released on September 19, 2006) Python includes a functional programming module, which adds support for easy partial function application.
>>> import functools >>> def plus(x, y): ... return x + y ... >>> add5 = functools.partial(plus, 5) >>> add5(37) 42
In older Python versions (2.1 and up), currying can be done using lambda functions:
>>> from __future__ import nested_scopes # this line required only for Python 2.1 >>> def curry(func, *curried_args): ... return lambda *args, **kw: func(*(curried_args+args), **kw) >>> def plus(x, y): ... return x + y ... >>> add5 = curry(plus, 5) >>> add5(37) 42
For still older Python versions, callable instances can be used to implement currying, using the __call__ method.
[edit] JavaScript
JavaScript code.
function plus(a,b){return a+b}
function curry(f,x){
return function(){
var arg=[x].concat(Array.prototype.slice.apply(arguments));
return f.apply({},arg);
};
}
alert(curry(plus,2)(3));
[edit] C#
This shows how to create syntactically natural currying functions in C#.
public delegate int Plus(int y);
public delegate Plus CurriedPlus(int x);
public static CurriedPlus plus =
delegate(int x) {return delegate(int y) {return x + y;};};
static void Main()
{
int sum = plus(3)(4); // sum = 7
int sum2= plus(2)(plus(3)(4)) // sum2 = 9
}
[edit] Perl
This is a Perl example of a curried function using a closure:
sub plus { $_[0] + $_[1] };
$plus5 = sub { plus(5,shift) };
print $plus5->(3); # prints 8
[edit] Mathematical view
When viewed in a set-theoretic light, currying becomes the theorem that the set <math>A^{B\times C}</math> of functions from <math>B\times C</math> to <math>A</math>, and the set <math>(A^B)^C</math> of functions from <math>C</math> to the set of functions from <math>B</math> to <math>A</math>, are isomorphic.
In other words, currying is the statement that product and Hom are adjoint functors; this is the key property of being a Cartesian closed category.
[edit] See also
[edit] External links
[edit] References
<references/>de:Currying fr:Curryfication ja:カリー化 zh:Curry化
