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 return a function with n-1 parameters. A function can either be thought of as having n arguments or a function with 1 argument that maps 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.

a function can be defined as f(x, y, z) -> g where it takes in three arguments x, y and z and returns q. To express this in curried form, the function would need to be split into multiple functions with only one argument. The new function can be written in the form f(x) -> (y -> (z -> q)). The function f takes in x as an argument and returns another function which takes in y as an argument. That function then returns another function which takes in z as an argument and returns q. A function, f(x, y, z) -> q, can be expressed in its curried form, F(x) -> (y -> (z -> q)).

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.

In contrast, there is also uncurrying. Uncurrying is a technique of transforming a one argument function into a function with many arguments.

The notion is that a function of n arguments can be thought of as a function of 1 argument that maps to a function of n−1 arguments

Background

Currying was first discovered by Moses Schönfinkel, a Russian Logician, in 1924[1] 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 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. In contrast a curried function takes in one parameter and returns ...

Currying in Programming

Currying is used in several programming languages.

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 [2].

Suppose we have 3 different functions:

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

            sum_ints = lambda do |a,b|
              s = 0 ; a.upto(b){|n| s += n } ; s 
            end

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

        sum_of_squares = lambda do |a,b|
          s = 0 ; a.upto(b){|n| s += n**2 } ;s 
        end

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

        sum_of_powers_of_2 = lambda do |a,b|
          s = 0 ; a.upto(b){|n| s += 2**n } ; s 
        end

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

        sum = lambda do |f,a,b|
          s = 0 ; 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 summation. The arguments 'a' and 'b' are used to define the lower and upper bound respectively. Now we can create the curried form of the 'sum' function.

        currying = sum.curry

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

        sum_ints = currying.(lambda{|x| x})
        sum_of_squares = currying.(lambda{|x| x**2})
        sum_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 [3].

References

[1] http://c2.com/cgi/wiki?CurryingSchonfinkelling

[2] http://www.khelll.com/blog/ruby/ruby-currying/

[3] http://www.haskell.org/haskellwiki/Currying