CSC/ECE 517 Fall 2011/ch1 2a sd

Introduction

Currying is a technique used in Computer Science and Mathematics to transform a function with multiple parameters into multiple functions with one parameter. 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.

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.

Mathematical Definition

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