Currying

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}$ , 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\colon (X\times Y)\to Z$ , and g is f after currying, then g has the type $g\colon X\to (Y\to 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\colon (X\times Y)\to Z$ and the morphisms to an exponential object $g\colon X\to 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.

Examples

Functional Languages

OCaml and F#

Functions are written in curried form by default in OCaml and F#:

  # (fun x y -> x+y) 2 3;;
  - : int = 5

In fact, the standard libraries define functions in curried form:

  # (+) 2 3;;
  - : int = 5

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.

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

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>

Scheme

This is a simple general currying function written in Scheme:

(define (curry f) 
  (lambda left-args
    (lambda right-args (apply f (append left-args right-args)))))

defines a function named curry which takes a single argument f and returns the function returning function (as per the definition).

This is an example of applying a curried function:

> (define increment ((curry +) 1))
> (increment 10)
11

Cat

This is a simple general currying function written in the stack-based functional programming language Cat:

  define partial_apply : ('b ('A 'b -> 'C) -> ('A -> 'C)) 
  { swap quote swap compose }

  define curry : (('A 'b -> 'C) -> ('b -> ('A -> 'C)) 
  { quote [partial_apply] compose }

This example explicitly demonstrates the relationship between partial application (which is argument binding or fixing) and currying.

Clean

Simple currying example in clean:

plus :: Int Int -> Int
plus x y = x + y

plus_one = plus 1

Start = plus_one 5 //will be 6

Languages from Other Paradigms

ALGOL 68

In 1968 C.H. Lindsey proposed for partial parametrisation for ALGOL 68, this is implemented as an extension in ALGOL 68G.

# Raising a function to a power #

MODE FUN = PROC (REAL) REAL;
PROC pow = (FUN f, INT n, REAL x) REAL: f(x) ** n;
OP ** = (FUN f, INT n) FUN: pow (f, n, );

# Example: sin (3 x) = 3 sin (x) - 4 sin^3 (x) (follows from DeMoivre's theorem) #

REAL x = read real;
print ((new line, sin (3 * x),  3 *  sin (x) - 4 * (sin ** 3) (x)))

C

#include <stdio.h>
#include <stdlib.h>

typedef struct cf
{
    void * function;
    int arguments_taken;
    int arguments_given;
    void ** arguments;

} curried_functor;

curried_functor* make_curriable(void * f, int arguments)
{
    curried_functor* currier = (curried_functor*) malloc(sizeof(curried_functor));

    currier->function = f;
    currier->arguments_taken = arguments;
    currier->arguments_given = 0;
    currier->arguments = (void**) malloc(arguments * sizeof(void*));

    return (currier);
}

curried_functor* curry(curried_functor* f, void* argument)
{
    int i;

    curried_functor* currier = (curried_functor*) malloc(sizeof(curried_functor));

    currier->function = f->function;
    currier->arguments_taken = f->arguments_taken;
    currier->arguments_given = (f->arguments_given + 1);

    currier->arguments =(void**) malloc(f->arguments_taken * sizeof(void*));

    for(i=0; i<f->arguments_taken; i++)
    {
        currier->arguments[i] = f->arguments[i];
    }

    currier->arguments[f->arguments_given]=argument;

    return (currier);

}

void evaluate(curried_functor* cf, void* argument, void* result)
{
    void* (*f)(void *[],void*);

    cf->arguments[(cf->arguments_taken - 1)] = argument;

    f = (void* (*)(void *[],void*)) cf->function;

    f(cf->arguments,result);
}

void sum(void* arguments[], void* result)
{
    int* target = (int*)result;

    *target = (*(int*)arguments[0] + *(int*)arguments[1]);
}

int main(void)
{

    int result;
    int a = 2;
    int b = 7;

    curried_functor* addN = make_curriable(&sum,2);
    curried_functor* add2 = curry(addN,&a);
    
    evaluate(add2,&b,(void*)&result);

    printf("%d", result);

    return (0);
}

C#

This shows how to create lambda expressions in C# using LINQ.

     Func<int, int, int> plus = (int x, int y) => x + y;
     Func<int, int> plus_one = (int x) => plus(x, 1);

     Console.WriteLine("RESULT=" + plus_one(3));

C++

The C++ Standard Template Library provides the function object (functor) multiplies which is used as follows:

  multiplies<int> multiply;
  cout << multiply(12, 25) << endl;

This function can be curried using one of the provided function object adapters, binder1st and binder2nd:

  binder1st< multiplies<int> > multiply12 = bind1st(multiply, 12);
  cout << multiply12(25) << endl;

Currying may also be achieved more generically using the Boost bind mechanism.

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

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)));
       }
   }

JavaScript

JavaScript code.

function addN(n) {
   return function(x){
      return x + n;
   }
}

add2 = addN(2);
alert(add2);
alert(add2(7));

Perl

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

sub curry {
    my ($func, @args) = @_;
    return sub { $func->(@args, @_) };
}

sub x_plus_y {
    my ($x, $y) = @_;
    return $x + $y;
}

my $x_plus_one = curry(\&x_plus_y, 1);
print $x_plus_one->(3), "\n";

Python

Creating closures in python:

def addN(n):
    return lambda x: x + n

>>> add2 = addN(2)
>>> add2
<function lambda at 0x009F1E30>
>>> add2(7)
9

Ruby

Simple currying example in Ruby:

def adder(x)
  lambda {|y| x+y}
end
a = adder(5)
a.call(10) # <= 15

Groovy

Simple currying example in groovy:

f = { a1, a2 -> a1 + a2 }
c = f.curry(7)
println c(2)

groovy> f = { a1, a2 -> a1 + a2 }
groovy> c = f.curry(7)
groovy> println c(2)

9

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.

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.

External links

Implicit currying in Scheme
Currying in Ruby
Currying in Smalltalk
Currying != Generalized Partial Application! - post at Lambda-the-Ultimate.org

References

^ I. Heim and A. Kratzer (1998). Semantics in Generative Grammar. Blackwell.

[1] I. Heim and A. Kratzer (1998). Semantics in Generative Grammar. Blackwell.

[1]