CSC/ECE 517 Fall 2011/ch1 2a ca

From Expertiza_Wiki
Jump to navigation Jump to search

Currying in mathematics is defined as the technique of breaking down a function that takes multiple parameters into a sequence of functions all of which take just one parameter. Similarly currying in computer science refers to the procedure of converting a function that takes n number of arguments into a chain of functions each of which takes a single argument. Currying was invented by Moses Schönfinkel and Gottlob Frege, and later rediscovered by Haskell Curry. The name "currying" was coined by Christopher Strachey in 1967.


Definition

Currying is defined as the technique of converting a function with multiple arguments into a function with fewer arguments. Currying, in general is performed by passing a lower order function with a single argument as a parameter to the next higher order function.

Suppose we have a function ƒ that takes in two parameters 

    ƒ(a, b) = a + b

Currying can be demonstrated by passing only one parameter to this function say 2 such that we get ƒ(2 ,b) which results in a new function g that takes in just one parameter i.e g(b) = ƒ(2, b) = 2 + b . And then passing a parameter to function g solves our initial equation g(3) = ƒ(2, 3) = 2 + 3. Notice how each of the function takes in just one argument.

By looking at the above example we can say that a curried function returns a new function when it is called with less than the expected number of arguments. And if the original function takes n number of arguments then the returned function would take n-1 number of arguments thus producing a sequence of functions as in lambda calculus.

In the context of a given programming language, to say that the programming language supports currying is to mean that the compiler understands the concept of currying to a certain degree. That is the programming language is inherently able to take a function with multiple arguments and break it down into server smaller functions each of which take a single argument.


Currying and Partial Application functions

Currying and Partial Application are two different approaches for transforming a given function into a new function usually with a smaller arity. They are often confused with each other.

Consider a function ƒ that takes in two arguments 

    ƒ: a × b → R

Currying takes the function ƒ and turns it into a new function g 

    g: a → (b → R)

Instead of calling ƒ with two arguments, we invoke function g with the first argument. The result is a function that we then call with the second argument to produce the final result. Thus, if the uncurried function ƒ is invoked as ƒ(2, 3). Then, the curried function g is invoked as g(2)(3)

Partial application on the other hand takes the same function ƒ and a fixed value a for the first argument to produce a new function 

    g: b → R

g does the same as ƒ, but only has to fill in the second parameter which is why its arity is one less than the arity of function ƒ.


For more clarity lets consider a function that takes three arguments. 

    ƒ: a x b x c → R

Now, currying the function ƒ turns it into a function g 

    g: a → (b → (c → R))

Calling g with just one parameter would return a function that would take one parameter and return another function.

In contrast for partial function, given the function ƒ and a fixed value a for the first argument, we get a new function g 

    g(y, z) → R

In the above case calling a partial function with just one argument returns a function that takes in two arguments which is clearly different to that of currying.

Thus we can say that a curried function is a function that will return a new function when it is called with less number of arguments than it expects and applying a function to less arguments than it expects is called partial function application. So, stated even more precisely, a curried function is a function that will return a new function when it is partially applied.


Advantages of Currying

The primary advantage of Currying is that it allows the programmer to invoke a function with fewer arguments than expected, thereby creating a new, possibly very useful function. For example, a function add which takes two arguments and adds them could be invoked with a single argument say 5 to create a new function that takes only one argument and which always adds five to that argument.

Currying improves code readability. Consider the following Haskell snippet. 

    lengths :: [[a]] -> [Int]
    lengths xs = map length xs
    

    lengths' :: [[a]] -> [Int]
    lengths' = map length

Removing the extra variable xs makes the code easier to read and there is no need to mentally keep clear what xs is.

Currying approach also allows us to write less code, with high level of maintainability. Consider the following example in Scheme. 

    (define (add a b)
      (action + a b))
    

    (define (mul a b)
      (action * a b))
    

    (define (action kind a b)
      (kind a b))

If the user code invokes add method, it in turn calls action with kind +. The same happens with mul method. All add does is wrapping the call to action with the appropriate kind. Now, consider curried definitions of these functions: 

    (define add-curried
      ((curry action) +))
    

    (define mul-curried
      ((curry action) *))

The functions have now become considerably shorter. We just curried the function action by passing it only one argument, the kind, and got the curried function which accepts the rest two arguments. Imagine that function action would immediately be rewritten to accept 3 more arguments. Without currying one would have to rewrite the implementations of add and mul. 

    (define (action kind a b c d e)
      (kind a b c d e))

Curried expressions can be understood locally - their dependence on their environment is entirely through their free variables. They tend to have fewer free variables and more bound variables than comparable imperative code, since they do not rely as heavily on assignment to express the computation. An imperative program proceeds by altering some globally-accessible store of values. By contrast, a functional program proceeds by function application and the return of values. This eliminates large classes of errors associated with maintaining a global store of values.


Applications of Currying

Currying can be implemented in any language that supports closures(lambdas), and is useful for partial function application like in UI programming where all the input necessary for the execution of function isn’t received, so a curried function is passed around with already received inputs captured in it.

Currying is particularly useful when we need to slowly build up our function over several different iterations.


Currying implementation in different languages

Currying in Declarative Languages like Functional Languages

Functional programming languages are a class of languages designed to reflect the way people think mathematically, rather than reflect the underlying machine.

Haskell

Consider a method of sorting which takes two parameters, the comparison function and the list to be sorted. Pick an element x, and divide the whole list into three parts. The first part has all elements that should go before x. The second part consists of all of the elements that are equal x. The third has the elements that ought to go after x. When the method ‘quickSort’ is applied to the list ‘sentence’, it gives the output as shown below. 

    sentence = [ “I”, “have”, “a”, “thing”, “for”, “Linux”] 
    quickSort usual sentence 
    

    Output
    [“I”, “Linux”, “a”, “for”, “have”, “thing”]

When the function is curried, we can apply only the comparison parameter. usualSort only remembers the comparison. Thus by just passing 'sentence' to usualSort, we get the required output. 

    usualSort = quicksort usual
    usualSort sentence
    

    Output
    [“I”, “Linux”,  “a” , “for” , “have” , “thing”]

Scheme

Scheme is one of the two dialects of LISP(the second oldest programming language).

The following function takes another function ‘f’ as a parameter and some number of arguments to be applied to ‘f’ as arguments. It returns a function which expects more arguments 

    (define (currying f . args)
             (lambda i
               (apply fun (append args i))))

Then a function to double a value can be curried as shown 

    (define double (currying * 2))
    (double 6)
    

    Output
    12

Currying in imperative languages

Imperative programming is a programming paradigm that describes computation in terms of statements that change a program state.

C#

C# is a general purpose Object Oriented Programming language. Consider the simple example of adding two numbers. 

    class Adding{
     delegate int Operation(int x, int y);
    

     static void Main(){
       Operation add = delegate(int x, int y){
         return x + y;
       };
       Console.WriteLine(add(13, 29));
     }
    }
    

    Output 
    42      //13+29

Now let us re-write the same code with currying technique. 

    class Adding{
    delegate Currying2 Currying (int x);
    delegate int Currying2(int y);
    

    static void Main()  {
     Currying add = delegate(int x)
     {
       return delegate(int y)
       {
         return x + y;
       };
     };
    Console.WriteLine(add(13)(29));
    }
   }
    

   Output
    42

JavaScript

JavaScript is a scripting language for client side programming of a web based application.

Taking the same example of adding two numbers, we have the function f that takes two parameters a1 and a2 and the curried function 'currying' that takes just one parameter and both producing the same output. 

    function f(a1, a2) {
     return a1 + a2;
    }
   
   

    function currying(a1) {
       return function (a2) {
             return f(a1, a2,);
       };
    }
   

    currying(5)(10);
    

    Output
    15

Let’s consider a practical example for currying in JavaScript

Consider a function 'currying' which take another function ‘f’ as a parameter and also a ‘scope’ variable. The function creates an array of arguments passed to it. 

    function currying (f, scope) {
     var scope = scope || window;
     var argArray = [];
     var length = arguments.length
     for (var i=2; i < length; ++i) {
        argArray.push(arguments[i]);
     };
    

     return function() {
     f.apply(scope, argArray); 
     };
    }

We can use the above 'Curried' function to a click event on the webpage 

    var x = document.getElementById('element');
    x.addEventListener('click', currying(greeting, x, 'Welcome'), false) 
    

    function greeting(msg) {
      window.alert(msg+'\n You clicked on '+this.id);
     }

Here the addEventListener waits for an external click on the ‘element’. When the button is clicked the ‘currying’ function is invoked which gathers the argument and then invokes the ‘greeting’ function

Ruby

Ruby is a dynamic scripting language that mainly runs on the Ruby on Rails framework. Ruby explicitly supports currying. Consider the example of adding two numbers. Normally the proc looks like this 

    plus = lambda { |a, b| a + b }
    puts plus [1, 2]
    

    Output
    3

Now we modify the program to fix one variable. Let us fix it to one and conveniently call it ‘incrementer’. 

    incrementer = lambda { |x| x+1 }
    puts incrementer.call(43)
    puts incrementer.call(57)
    

    Output
    44
    58

In Ruby 1.9, you create a curry-able proc by calling the curry method on it. If you subsequently call this curried proc with fewer parameters than it expects, it will not execute. Instead, it returns a new proc with those parameters already bound. Consider the following example written in Ruby 1.9, taken from PragDave, which curries the 'plus' proc. 

    curried_plus = plus.curry  
    # create two procs based on plus, but with the first parameter   
    # already set to a value  
    plus_two = curried_plus[2]  
    plus_ten = curried_plus[10]  
    

    puts plus_two[3]  
    puts plus_ten[3] 
    
 
    Output
    5
    13


References

1. Currying - Wikipedia
2. Currying and Partial Function Applicationat MSDN Blogs
3. Currying-vs-Partial function at 2ality by Dr. Axel Rauschmayer.
4. Why I love Currying blog at amateurtopologist.com
5. Currying - HaskellWiki
6. Fun with Procs in Ruby 1.9 at PragDave by Dave Thomas

Further Reading

Language Specific Implementations

Retrieved from "https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_517_Fall_2011/ch1_2a_ca&oldid=50028"