CSC/ECE 517 Fall 2011/ch1 2a sd

Currying

Currying is a technique used in Computer Science and Mathematics to transform a function with n parameters into a function with one parameter. This new function would map to another function with n-1 arguments. For example, we can define a function as add(x, y) -> x + y. This function takes in two parameters, x and y, and returns x + y. If we wanted to evaluate add(3, 4) here is how we would do it:

   add(3, 4) ↦ x + y
   = 3 + 4 = 7

The function is evaluated all in one step. The curried form of this function would be: add(x) -> (y -> x + y). The add function takes in one parameter, x, and returns another function taking in y. The second function then returns the result x + y. If we wanted to evaluate add(3, 4) in curried form, the following steps should be taken:

   add(3) ↦ (y ↦ x + y)
   = 4 ↦ 3 + y
   = 3 + 4 = 7

The curried function is evaluated in two steps instead of one. Also, x is treaded like a constant in the second function.

As shown in the given example, the curried and uncurried form of the add function produce the same result. Another thing to note, a function can be curried but also a curried function can be uncurried. To transform a curried function into an uncurried one, we just need to reverse the steps.

Background

Currying was first discovered by Moses Schönfinkel, a Russian Logician, in 1924<ref>http://c2.com/cgi/wiki?CurryingSchonfinkelling</ref> and later re-discovered by Haskel Curry, an American Mathematician and Logician. Although Schönfinkel was the first to discover it, the process was ultimately named after Curry. For this reason, some people thought a more appropriate name would be Schönfinkeling.

Currying in Math

Currying is used throughout Mathematics. Most notably, currying is used in lambda calculus. Lambda calculus borrows the idea that every function can only have one parameter<ref>http://en.wikipedia.org/wiki/Lambda_calculus</ref>.

Currying v.s. Partial Function

There is a small distinction between currying and partial functions. A Partial function simplifies another function by making one or more of its arguments constant. Suppose we have a function, f(x, y, z) -> x + y + z. If we were to curry the function, we would get f(x) -> (y -> (z -> x + y + z)). To create a partial function, we can set x, y, and/or z to a constant value. If we wanted to require x to always be 1, we remove x as a parameter and set it to 1 as follows: f(y, z) -> 1 + y + z. One thing to point out is curried functions can only have one parameter while partial functions can have one or more<ref>http://en.wikipedia.org/wiki/Partial_function</ref>.

Currying in Programming

Currying can be used in programming to simplify the code and make it easier to read. This reduces code repetition by combining the common parts of different function into one. Many different programming languages used today implement currying. Currying is most evident in functional programing languages. Other languages such as java and c++ do not have built in support for currying. Shown below is a couple of languages and their implementations of currying.

Ruby

In ruby 1.9, the curry method was added to procedure objects. Previous versions of ruby do not have a dedicated curry function. Here is an example of using the curry function in Ruby <ref>http://www.khelll.com/blog/ruby/ruby-currying/</ref>.

Suppose we have 3 different functions:

1. product_ints: this function takes in two arguments, a and b, and determines the product of all integers between a and b.

        product_ints = lambda do |a,b|
          s = 1 ; a.upto(b){|n| s *= n } ; s 
        end

2. product_of_squares: this function takes in two arguments, a and b, and returns the product of the square of the integers from a to b.

        product_of_squares = lambda do |a,b|
          s = 1 ; a.upto(b){|n| s *= n**2 } ;s 
        end

3. product_of_powers_of_2: this function takes in two arguments, a and b, and returns the product of the powers of two from a to b.

        product_of_powers_of_2 = lambda do |a,b|
          s = 1 ; a.upto(b){|n| s *= 2**n } ; s 
        end

We can note that each function follows a similar pattern. They all use the product of a sequence of numbers from a to b. We can pull this functionality out and write one main function that all three functions will use:

        product = lambda do |f,a,b|
          s = 1 ; a.upto(b){|n| s *= f.(n) } ; s 
        end

This function takes in three arguments: f, a, and b. The argument 'f' is the function we want to use on each element in the multiplication sequence. The arguments 'a' and 'b' are used to define the lower and upper bound respectively. Now we can create the curried form of the 'product' function.

        currying = product.curry

With this currying function we can create the three partial functions defined above.

        product_ints = currying.(lambda{|x| x})
        product_of_squares = currying.(lambda{|x| x**2})
        product_of_powers_of_2 = currying.(lambda{|x| 2**x})

Haskell

In Haskell, all functions are in curried form. In other words, all functions take just one argument. This notion is mainly hidden from the user. For instance, we can divide two numbers, 8 and 4, by calling 'div 8 4'. The function does not take in two number and return the result as one would think. In Haskell, the 'div' function is defined as:

        div :: int -> int -> int

The three integers above represent the first argument, the second argument, and the result respectively. The division is computed in two steps. First the function 'div' evaluates the first argument, 8, and returns a function of type 'int -> int'. This new function is then applied to the second argument, 4, and returns the result of 2 <ref>http://www.haskell.org/haskellwiki/Currying</ref>.

JavaScript

In javaScript, there is no built-in currying function. However, we can create a curried function manually by using the idea that methods can return other methods. For instance, if we have an uncured add function as described below,

   var add = function(a, b) {
       return a + b;
   };

we can curry the function by returning another function. The curried form of the add function is shown below <ref>http://extralogical.net/articles/currying-javascript.html</ref>:

   var curriedAdd = function(a) {
       return function(b) {
           return a + b;
       };
   };

ML

ML stands for Metalanguage. In ML all anonymous functions are curried. An anonymous function is a function that has no name and can only take one parameter Shown below is an example of an anonymous function:

   val add = (fn x => (fn y => x + y));

We can also represent this function in its uncurried form by not using anonymous functions <ref>http://www.svendtofte.com/code/curried_javascript/</ref>:

   fun add x y = y + x

Conclusion

As we discussed in this article, there are many advantages to using currying.

Advantages

1. Makes code easier to read
2. Allows for easy creation of partial functions
3. A method can still be executed even if all its parameters are not known.
4. Simplifies the method call of functions
5. Condenses code by eliminating duplicated statements

Currying is used throughout Mathematics and Computer Science. It is the underlying idea behind the programming language Haskel as well as lambda calculus. Currying is a very powerful tool that, if used correctly, can greatly simplify a function.

References

<references />