Saturday, December 24, 2016

Exploring Currying and Partial Application using Scala

tl;dr

  1. Currying is different from Partial (Function) Application.
  2. In Scala, it is possible to define a function that returns another function which can be called with arguments. Although this might look similar, it is not necessarily the same thing as either Currying or Partial (Function) Application.
  3. What is currying? It is a process whereby the multiple arguments required by a function are passed in, one at a time, instead of the typical process of calling the function by supplying all its arguments at once.

    val volume = 
    (length: Double, breadth:Double, height: Double) => length * breadth * height
    
    // called with the required argument at once
    volume(1,2,3) 
    
    // creates a curried version of the function
    val curriedVersion = volume.curried
    
    // with the curried version we can pass in the arguments one after the other
    
    // pass first argument
    val withFirstArg = curriedVersion(1) 
    
    // and now with second argument
    val withFirstArgAndSecondArg = withFirstArg(2)
    
    // and now with third argument which yields the result
    val volumeValue: Double = withFirstArgAndSecondArg(3) 
    
    
  4. Partial Application what is it? It is possible to take a function that expects multiple arguments and pre-fill some of these arguments. Doing this, returns a function that can then be called by supplying the remaining argument(s) that were not pre-filled.

    val volume = 
    (length: Double, breadth:Double, height: Double) => length * breadth * height
    
    // called with the required argument at once
    volume(1,2,3)
    
    // first and second argument pre-filled
    val withFirstAndSecondArgsSet: (Double) => Double = volume(1,2,_)
    
    // now third argument is supplied and result evaluated
    val volumeValue: Double = withFirstAndSecondArgsSet(3) 
    
  5. Currying can then be seen as a specialised outcome of Partial Application. The resulting function of Partial Application can have any number of arguments. With Currying it has to be a chained sequence of functions that take one argument at a time.
  6. Currying can also be seen as a sequence of Partial Application where each step involves partially applying only one of all possible arguments defined by the function.
  7. Partial (Function) Application is different from partial functions.

What is Currying

I like to think of currying as a process, in which I am able to pass in the multiple arguments required by a function, one at a time, through a chain of functions that only accepts one argument, till all the required arguments are supplied to the function. This then leads to the evaluation of the function to produce its result.

Wikipedia says the following about currying:

In mathematics and computer science, currying is the technique of translating the evaluation of a function that takes multiple arguments (or a tuple of arguments) into evaluating a sequence of functions, each with a single argument.

Which is more or less what I described above.

How does this look in Scala code?

Let’s look at the definition from Wikipedia again:

In mathematics and computer science, currying is the technique of translating the evaluation of a function that takes multiple arguments

Before going forward, we will define such a function that takes multiple arguments. This function will be used for our illustration.

I suggest the simple function used to calculate the volume of a cuboid. It takes multiple arguments: length, breadth and height. That is:

val volume = 
(length: Double, breadth:Double, height: Double) => length * breadth * height

With the function that would be used for illustration defined, let us now go back to what's left of the definition of currying from Wikipedia:

...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

The volume function thus defined above, can be evaluated by supplying all its arguments:

volume(1,2,3) // evaluates to 6

This evaluation is done by passing in all the required arguments in a single go. But with currying, this is not want we want. Instead, we want to translate the evaluation of this function into series of steps, where we can pass in each argument, one at a time, till all the 3 arguments have been supplied. And during this process, a function which takes just one argument must be returned, each step of the way.

How can this be done?

Using the curried method

In Scala, every function has a curried method which can be used to do this conversion for us. So we would have:
val volume = (length: Double, breadth:Double, height: Double) 
                                           => length * breadth * height
val curriedVolume = volume.curried

With this curriedVolume we can now evaluate the volume of a cuboid, by first passing in the length, followed by the breadth and finally the height. Let’s see how that looks:

val volume = 
(length: Double, breadth:Double, height: Double) => length * breadth * height

val curriedVolume = volume.curried

// with the curried version we can pass in the arguments one after the other
val length = 1
val breadth = 2
val height = 3

// pass first argument
val withFirstArg = curriedVolume(length)

// and now with second argument
val withFirstArgAndSecondArg = withFirstArg(breadth)

// and now with third argument which yields the result
val volumeValue: Double = withFirstArgAndSecondArg(height)

The same sequential passing of arguments can also be achieved by chaining the function call:

val volumeValue: Double = curriedVolume(length)(breadth)(height)

Using multiple parameter lists

In Scala it is possible to define a method/function parameters as separate multiple parameter list. For example instead of having:

def sum(x: Int, y: Int) = x + y
we have:
def sum(x: Int)( y: Int) = x + y

This syntax allows us to pass the multiple arguments required by a function one after the other, with each step returning a function that takes the next argument.

Applying this to our volume function we would have:

val volume = 
(length: Double, breadth:Double, height: Double) => length * breadth * height

def curriedVersion(length: Double)(breadth: Double)(height: Double) = 
                                                   volume(length, breadth, height)

We can then call this curriedVersion function like we did the one that was created by curried method above:

val volume = 
(length: Double, breadth:Double, height: Double) => length * breadth * height

def curriedVersion(length: Double)(breadth: Double)(height: Double) = 
                                                 volume(length, breadth, height)

// with the curried version we can pass in the arguments one after the other
val length = 1
val breadth = 2
val height = 3

// pass first argument
val withFirstArg: (Double) => (Double) => Double = curriedVersion(length)

// and now with second argument
val withFirstArgAndSecondArg: (Double) => Double  = withFirstArg(breadth)

// and now with third argument which yields the result
val volumeValue: Double = withFirstArgAndSecondArg(height)
// note that in this examples, type annotations are required. 
// The reason, will be the subject matter of another blogpost

In the example above the curriedVersion was defined, with a def. What if you want to define the function using function literals?

Doing that won’t work:

val curriedVersion = 
(length: Double)(breadth: Double)(height: Double) => volume(length, breadth, height)

The right way to define a curried function using the function literal syntax will be:

val curriedVersion = 
(length: Double) => (breadth: Double) => (height: Double) => 
                                                    volume(length, breadth, height)

// annotated with the type signature:
val curriedVersion: (Double) => (Double) => (Double) => Double = 
  (length: Double) => (breadth: Double) => (height: Double) => 
                                                    volume(length, breadth, height)

Which makes sense, because if we look at the type (Double) => (Double) => (Double) => Double, we have a function which takes a Double to return a function that takes the second Double, which returns a function that takes the third Double. And this third function, returns the evaluated Double for the function: exactly what currying is.

With this, we move over to Partial Application (which could also be referred to as Partial Function Application).

What is Partial (Function) Application

We usually refer to the execution of a function as calling the function. If the function requires any argument(s), then we say calling the function with its arguments.

A more formal description of this, is to say the function is applied to its arguments.

The definition from wikipedia puts function application as:

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.

So instead of saying calling a function, we can as well say, apply the function.

Partial Application is thus the process of applying a function, to part of the arguments it defines, returning a function, which can then be applied to the remaining arguments needed by the original function.

Definition of Partial Application from Wikipedia says:

In computer science, partial application (or partial function application) refers to the process of fixing a number of arguments to a function, producing another function of smaller arity.

Said in another way, partial application is the process of calling a function by providing it with part of the arguments it needs to return a function that can then be called with the remaining arguments.

In Scala code, this looks thus:

val volume = 
(length: Double, breadth:Double, height: Double) => length * breadth * height

val length = 1
val breadth = 2
val height = 3

//1.0 with all the argument given at once
val volumeValue = volume(length, breadth, height)

//2.0 with length pre-filled
val fnWithLength = volume(length, _:Double, _:Double)

//2.1 with breadth and height later supplied
val volume1 = fnWithLength(breadth, height)

//3.0 with length and breadth pre-filled
val fnWithLengthAndBreadth = volume(length, breadth, _:Double)

//3.1 with height later supplied
val volume2 = fnWithLengthAndBreadth(height)
// note also the type annotation following the _, i.e _:Double. 
// without them you will get a compilation error
// The reason hopefully will be the topic of another blogpost

Difference between Currying and Partial (Function) Application

Haven given the definitions of Currying and Partial (Function) Application, the difference between the two concepts should be a little clearer now. Currying is about turning a multi-argument function into a chain of single argument function, while Partial (Function) Application is about pre-filling arguments of a function is that it can be later called with its other arguments supplied.

Formally, Currying is:

Giving a function 
f:(X×Y×Z)→N

Currying is:
curry(f):X→(Y→(Z→N)) 

While for partial application:

Giving a function 
f:(X×Y×Z)→N
partial application is:
partial(f):(Y×Z)→N

Why then, do these concepts appear confusing?

Apart from the fact that both can be seen as a mechanism to provide a more specialised version of a general function, I will say one of the contributing factor to the confusion is the fact that, with a function with two arguments, the two concept might appear indistinguishable.

And unfortunately, I have seen quite a lot of posts that tries to explain these two concepts using functions that takes two arguments. Even the example on the official tutorial on scala-lang makes use of a function that takes two arguments!

The, almost canonical example you run into is the add function.

Something like this:

// partial application
def add(x: Int, y: Int) = x + y
val add5 = add(5, _)
println(add5(3)) //prints 8


//and same example for currying:
def add(x: Int)(y: Int) = x + y
val add5 = add(5)
println(add5(3)) // prints 8

As you can see, this is an example that does not really make obvious, the difference between the two concepts. 

Partial Application and Partial Function. The difference

I will end by pointing out that there exist another concept called Partial Function, which is in no way related to Partial application.

Partial function, and the various mechanism Scala provides to work with it, is a topic worthy of it’s own post, so I would not go into its details here. I will only summarise what partial functions are so as to make it clear how it is different from Partial Application.

Functions can be seen as a mapping between input values and result values.

def doubleIt(x:Int): Int = x * x
// the doubleIt function maps 
// 2 to 4
// 500 to 1000
// etc etc. 

A function that has the ability to map all its inputs to a result is called a total function. The doubleIt function above is an example of a total function.

A function which cannot produce result values for some of its input is called a partial function. For example, a squareRoot function:

def squareRoot(x: Int): Double = Math.sqrt(x)
// which maps all positive integer to a value
// but can’t map any negative integer to a value
// for example what would be the square root of -4?

Or a divisor function like this:

def divisor(num:Int, div:Int): Int = num / div
// which is a partial as it cannot map to a result if div is 0
// you will get a java.lang.ArithmeticException instead

These are all examples of Partial Function, and as can be seen, are totally different and in no way related to Partial Application.

2 comments:

robinloxley said...

Great explanation.

Sait Sami KocataƟ said...

thanks for the post, very informing