Currying

From Wikipedia, the free encyclopedia

This article is about the method of transforming functions. For the cooking technique, see Curry.

In mathematics, computer science and linguistics (semantics), currying or Schönfinkelisation^[1] is the technique of transforming a function that takes multiple arguments into a function that takes a single argument (the other arguments having been specified by the curry). The technique was named by Christopher Strachey after logician Haskell Curry, though it was invented by Moses Schönfinkel and Gottlob Frege.

Simply put, currying is the transformation of an input into a new function, the new function requiring another input of course. For example $f (x) = g x (y)$ , where $g x (y) = x + y$ . Therefore you can say that $f (x)(y) = x + y$ , which means that instead of using a 2 dimensional cartesian input, ie $f (x, y)$ , you are using a 1 dimensional input and giving the output another input which will finally produce the result sought.

If a function f has the type f : (X × Y) → Z, and g is f after currying, then g has the type 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 can be found in the universal property of an exponential object, which gives rise to the following adjunction in cartesian closed categories : There is a natural isomorphism between the morphisms from a binary product f : X × Y → Z and the morphisms to an exponential object g: X → Z ^Y.

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 have built-in syntactic support for currying, where certain multi-argument functions are expanded to their curried form; notable examples are ML and Haskell. Any language that supports closures, including Lisp, Scheme, Eiffel, Perl, Ruby, Python, R, S, Groovy, Smalltalk 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 its previous approach based on its lambda operator.

1 Examples
- 1.1 Eiffel
- 1.2 Haskell
- 1.3 ML
- 1.4 Scheme
- 1.5 C#
- 1.6 C++
- 1.7 JavaScript
- 1.8 Perl
- 1.9 Java
- 1.10 Io
2 Mathematical view
3 See also
4 External links
5 References

[edit] Examples

[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] Haskell

Likewise in Haskell, function type signatures show the currying-based structure of functions (note: "\ ->" is Haskell's syntax for anonymous functions, in which the sign \ has been chosen for its resemblance to the Greek letter λ (lambda); it is followed by a list of space-separated arguments, and the arrow -> separates the arguments list from 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] ML

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>

[edit] Scheme

This is a simple general currying function written in Scheme:

;curry:function,args->(function)
;Adding using currying 

(define (curry f . args) (lambda x (apply f (append args x))))

This is an example of applying a curried function:

>((curry + 10) 10)
20

[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] 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] 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] Perl

This is a Perl 5 example of a general curry function and curried plus using closures:

sub curry{
  my ($func, @args) = @_;

  sub {
    #This @_ is later
    &$func(@args, @_);
  }
}

sub plusXY{
  $_[0] + $_[1];
}

my $plusXOne = curry(\&plusXY, 1);
print &$plusXOne(3), "\n";

[edit] Java

Java programming language code.

   public class Currier<ARG1, ARG2, RET> {
       public interface CurriableFunctor<ARG1, ARG2, RET> {
           RET evaluate(ARG1 arg1, ARG2 arg2);
       }
   
       public interface CurriedFunctor<ARG2, RET> {
           RET evaluate(ARG2 arg);
       }
   
       final CurriableFunctor<ARG1, ARG2, RET> functor;
   
       public Currier(CurriableFunctor<ARG1, ARG2, RET> fn) { functor = fn; }
       
       public CurriedFunctor<ARG2, RET> curry(final ARG1 arg1) {
           return new CurriedFunctor<ARG2, RET>() {
               public RET evaluate(ARG2 arg2) {
                   return functor.evaluate(arg1, arg2);
               }
           };
       }
   
       public static void main(String[] args) {
           Currier.CurriableFunctor<Integer, Integer, Integer> add
               = new Currier.CurriableFunctor<Integer, Integer, Integer>() {
                   public Integer evaluate(Integer arg1, Integer arg2) {
                       return new Integer(arg1.intValue() + arg2.intValue());
                   }
           };
           
           Currier<Integer, Integer, Integer> currier
               = new Currier<Integer, Integer, Integer>(add);
           
           Currier.CurriedFunctor<Integer, Integer> add5
               = currier.curry(new Integer(5));
           
           System.out.println(add5.evaluate(new Integer(2)));
       }
   }

[edit] Io

A general currying function written in the Io programming language:

curry := method(fn,
        a := call evalArgs slice(1)
        block(
                b := a clone appendSeq(call evalArgs)
                performWithArgList("fn", b)
        )
)

// example:
increment := curry( method(a,b,a+b), 1 )
increment call(5)
// result => 6

[edit] Mathematical view

When viewed in a set-theoretic light, currying becomes the theorem that the set $A^{B\times C}$ of functions from $B\times C$ to $A$ , and the set $(A B) C$ of functions from $C$ to the set of functions from $B$ to $A$ , are isomorphic.