All Articles

Currying

Intro

I will discuss how multivariate functions are typically worked with in functional programming. In particular, the notion of currying will be explored.

Multi-arity functions

The arity of a function is the number of arguments that the function takes. Functions with no arguments (referred to as nullary functions) have an arity of 0. Single-variable functions are referred to as unary functions and have an arity of 1.

Most functions take more than one variable. Such functions are referred to as multi-arity functions.

In particular, functions which have an arity of 2 or 3 are often referred to as binary and ternary functions, respectively.

Let

f:(X×Y)Zf : (X\times Y) \rightarrow Z

be a binary function.

Such a function takes a pair (x,y)X×Y(x,y)\in X\times Y as its argument and outputs an element f(x,y)=zZf(x,y) = z \in Z.

Suppose I want to evaluate ff at the point (x0,y0)(x_0,y_0).

I could explicitly pass both arguments to ff and compute the result directly.

Functional programming approaches this from a slightly different point-of-view (for reasons which will be discussed shortly).

Rather than passing the pair (x0,y0)(x_0,y_0) to ff directly, one first passes only x0x_0 to ff, returning f(x0,y)f(x_0,y). But f(x0,y)f(x_0,y) is itself a function from YZY \to Z. Let f(x0,y)=h(y)f(x_0,y) = h(y). One then passes y0y_0 as an argument to hh which results in h(y0)=f(x0,y0)h(y_0) = f(x_0,y_0).

In this way the evaluation of the multivariate function ff at (x0,y0(x_0,y_0) is divided into two separate univariate evaluations.

If we let YZY\to Z represent the set of all functions from YZY\to Z then we can define

fcurried:X(YZ)f_{\text{curried}}: X \to (Y\to Z)

to be the curry of ff.

Ex

Let f(x,y)=x+y:(Z×Z)Zf(x,y) = x + y : (\mathbb{Z} \times \mathbb{Z}) \to \mathbb{Z}.

Let (x0,y0)=(1,1)(x_0,y_0) = (1,1).

We want to evaluate

fcurried:Z(ZZ)f_{\text{curried}} : \mathbb{Z} \to (\mathbb{Z} \to \mathbb{Z})

at (x0,y0)(x_0,y_0).

First,

fcurried(1)=1+yf_{\text{curried}} (1) = 1 + y

Next,

fcurried(1)(1)=1+1=2f_{\text{curried}}(1)(1) = 1 + 1 = 2

Note that in the first evaluation x0=1x_0=1 is the input and the function h(y)=fcurried(1)h(y) = f_{\text{curried}}(1) is the output.

In the second step the function h(y)h(y) is itself evaluated at y0=1y_0=1 resulting

So, that’s currying.

The General Case

Let

f:(X×Y×Z)Nf : (X\times Y\times Z) \to N

be a ternary function, for some sets X,Y,Z,NX,Y,Z,N.

We will iteratively curry this function.

(X×Y×Z)N=X((Y×Z)N)two-variable function=X(Y(ZN))\begin{aligned} (X\times Y\times Z) \to N &= X \to \underbrace{\big((Y\times Z) \to N\big )}_{\text{two-variable function}} \\ &= X\to \big(Y\to (Z\to N)\big) \end{aligned}

One can iteratively apply the above argument for nn arguments. The right-associativity is generally implicitly understood so that the parentheses are normally omitted.

Currying in action

For each of the below examples we will consider a simple addition function function f(x,y)=x+yf(x,y) = x + y.

Haskell

Without currying

add :: (Int, Int)  -> Int
add(x,y) = x + y

With currying

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

Evaluation

main :: IO ()
add :: Int -> Int -> Int
add x y = x + y
add_ = add 1
main = print (add_ 1)  -- 2

Alternating

Uncurried ⟶ curried:

main :: IO ()

add :: (Int, Int)  -> Int
add(x, y) = x + y

addCurried = curry add
addCurried_ = addCurried 1

main = print (addCurried_ 1) -- 2

Curried ⟶ uncurried

main :: IO ()

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

add = uncurry addCurried

main = print (add(1,1)) -- 2

Scala

Without currying

    val add = (x: Int, y: Int) => x + y

With currying

    val addCurried: Int => Int => Int = x => y => x + y

Evaluation

    val add: Int => Int => Int = x => y => x + y
    val add_ = add(1)(_)
    println(add_(1)) // 2

Alternating

Uncurried ⟶ curried:

    val add = (x: Int, y: Int) => x + y
    val addCurried = add.curried
    println(addCurried(1)(1)) // 2

Curried ⟶ uncurried:

    val addCurried: Int => Int => Int = x => y => x + y
    val add =  Function.uncurried(addCurried)
    println(add(1, 1)) // 2

Partial Function Application vs Currying

One often sees the notion of partial function application discussed alongside currying. While they may seem similar, in reality they are different.

Currying takes an nn-ary function and transforms it into nn unary functions. Partial function application takes an nn-ary function, evaluates it for some subset of the arguments (say xx of them) and returns an (nx)(n-x)-ary function.

Example

    val add = (a: Int, b: Int, c: Int) => a + b + c
    val addPartial = add(1, _: Int, _: Int)

    println(addPartial(1,1))   // 3

Note how partial application mapped a ternary function to a binary function, whereas the curry of add would map an argument to a unary function to a unary function, as below.

    val add: Int => Int => Int => Int = x => y => z => x + y + z
    val addPart = add(1)
    val addPart_ = addPart(1)

    println(addPart_(1))  // 3

Why Curry

Now that we understand what currying is and what it is not, the question remains, why bother currying at all?

In short, currying makes it syntactically easier to work with higher order functions, which will be discussed in a future post.

Published 12 Jun 2018