Functional Programming in C# - Currying

  • Article

Everytime I make a post about C# or any other statically typed language, I get hit by a ton of comments from dynamic and functional language programmers who look down upon me for using a statically typed language(*cough*, *cough* ;-) ). And being a big fan of Python and 'the Lisp way' myself, I have to admit that there are times when I miss the higher-order function support I get in languages like Haskell.

Until now that is :-)

With C# 2.0, you get something called anonymous delegates. On the surface, this seems to be syntactic sugar around writing a delegate. But in reality, there is something more magical going on underneath the covers - something called 'closures'. However, C# anonymous methods are not closures in the true sense of the word.

And thanks to these closures, we can do things now in C# 2.0 that we could only dream about in other statically typed languages .(see Don's post for some cool things that become possible). For example, currying. If curry conjures up images of spicy Indian food, head on over to this Wikipedia article to see what I'm talking about.

Instead of explaining currying again, let me point to a blog post I made in an earlier life where I talked about implementing this in Python.

Basically, currying refers to function builders. Instead of writing a series of functions which differ slightly, you can write one uber-cool function and have it generate functions for you at runtime.

Now, let's see how we can do the same currying in C# 2.0. I really don't care how the code for the curry() function looks like but I want the actual function invocation to have the same syntax as it does in Python.

Curry when implemented in C# 2.0 looks something like this

 public class Lambda
{
public delegate T Function<T,T1>(params T1[] args);

public static Function<K,K1> Curry<K,K1>(Function<K,K1> func, params K1[] curriedArgs)
{
return delegate(K1[] funcArgs)
{

                    //Create a final array of parameters, having the curried parameters at the beginning, followed
// by the arguments at the time the generated delegate is called

K1[] actualArgs = new K1[funcArgs.Length + curriedArgs.Length];
curriedArgs.CopyTo(actualArgs, 0);
funcArgs.CopyTo(actualArgs, curriedArgs.Length );

//Call the function with our final array of parameters.
return func( actualArgs );

};

}

}

Things to note here

  • 'K' is the return type of the function that is going to be curried. K1 is the type for the param array

I know that the code doesn't look as friendly as the Python code but hey, I'll take what I can get.:-) Also, since this code will probably lie in some library somewhere, the complexity is not really a factor.

The only problem I ran into was that anonymous delegates can't use param arrays but that didn't matter in the end. The syntax for variable length arguments isn't as friendly as it is in Python but then, I doubt that Anders anticipated them to be used this way in C# :-)

Now that we have written ourselves a handy-dandy curry function, let's take it for a spin. Similar to the Python multiply example above, I want a adder-builder function.

Let's write the actual function first. This takes any number of integers and returns the sum of all of them.

 public static int Add (params int[] numbers)
{

int result =0;
foreach (int i in numbers)
{
result += i;
}

return result;
}

I want to modify this Add function so that it not only adds all its parameters but it also adds 7 to the result and returns the answer (talk about contrived examples :-) ). Instead of writing a wrapper function, I can just go ahead and use our shiny new Curry method.

 Lambda.Function<int,int> adder=Lambda.Curry<int,int>(Add,7);
adder(5, 6); // returns 18

What's happening here? Our 'Curry' function generates a new function for us which appends 7 to the parameter list. When we invoke the 'adder' delegate with 5 and 6 as the arguments, in reality, we're calling Add with 5,6 and 7 as the parameters. The magic part is that you can create another curry passing this 'adder' delegate. Want to add '2' to whatever 'adder' returns? You can go ahead and do this

 Lambda.Function<int,int> adder2 = Lambda.Curry<int,int>(adder, 2);
adder2(5, 6); //returns 20 ( 5+ 6 + 7 + 2)

 

Mind-bending stuff. :-)

Update: Changed the code to a generic method instead of a generic class as suggested by Don Box

Update: Linked to Brad's post on why anonymous methods are not closures

Comments

  • Anonymous
    August 07, 2005
    check this out as this is very useful implementation

  • Anonymous
    August 07, 2005
    Hey, paul graham's book onlisp, talks about doing the same thing as you've done in this blog post, but just that he manages to do that with ...hmm.. say like 3-4 lines of code!

    I am not saying C# is a bad language.. but just that static typing is not really suited to do this sort of thing without the added baggage of verbosity :)..

    Anyway, its not like developers are new to dynamically typed languages (atleast most from web-dev are) .. maybe MS should release VS.NET with say LISP (they can call it L# if they want to).

    See, MS's marketing might is what it needs to put LISP in the driving seat. and maybe they won't look evil anymore :D

  • Anonymous
    August 07, 2005
    Nice implementation Sriram. The point to note is that now that C# has some approximate form of closures, a lo tof things that were accomplished by closures in other languages (sometime under the hood) now become possible.

    Vishnu, if the code Sriram wrote was part of the of BCL then you would see C# do something like currying in about the same 3 or 4 lines. :)

  • Anonymous
    August 07, 2005
    If you were willing to not use the params keyword, you could specify a set of generic functions:

    Curry<K>
    Curry<K, T1>
    Curry<K, T1, T2>
    .. etc

    which should then allow you to vary the strong typing by parameter. I can see also a way to do this using the Lightweight Code Generation features. Haven't had time to verify, though.

  • Anonymous
    August 07, 2005
    Vishnu - if you look at Paul Graham's code and my code on the client side, you'll see that it is almost the same code. And I doudbt a commercial language's implementation of curry will be as simplistic as Paul Graham makes it out to be. Like Roshan says, all this will be hidden in a class library for you. Remember - you're getting all this goodness + static typing - so that's a win-win situation

    KFarmer - In actual production code, that's what I would do since I would have a fair idea of the number of parameters required beforehand. In this example, I wanted to make it as generic as possible

  • Anonymous
    August 07, 2005
    The comment has been removed

  • Anonymous
    August 08, 2005
    hmm... polite rebuttal for your currying code.. (I know you are lisp/scheme enthusiast, but just to debunk the 5 lines argument, you had to reinvent lambda, and I din't.)

    (define (curry-adder x) (lambda(z)(+ x z)))
    (define add7 (curry-adder 7))
    (add7 10)

    ;; If i was a member of the Knights of lambda calculus, maybe i could do this in lesser lines :)

    anyway, I read your friend's post on doing something similar in C++

    Well, actually I did post on something very similar.. which can be much more easily extended to do currying and can still do a nice job of closures..

    Its here : http://www.livejournal.com/~vishnuvyas/10765.html

    now probably add continuations to C++ and we C++philes can catch up to the 60's :D.

  • Anonymous
    August 08, 2005
    oh, btw about your static typing argument..

    you can type in CommonLisp, also gcl does type-inference, so power of static typing + ease of expression at dynamic typing.

    (according to the paper you sent me, typeinference seems to be still inside MS research :D)

    and isin't this discussion getting a bit too discursvie?

  • Anonymous
    August 08, 2005
    The comment has been removed

  • Anonymous
    September 04, 2005
    What you've done here isn't currying, it's partial function application. Currying is the process of converting a n-argument function f into a single-argument which takes a parameter p1, and returns a single-argument function which takes a parameter p2, and ... returns a single-argument function which takes a parameter pn, and returns f(p1, p2, ... , pn).

    So, if you had:

    public static int Add (int a, int b)
    {
    return a + b;
    }

    then a correct implementation of Curry would mean that Curry(Add)(1)(2) would return 3.

    Incidentally, python2.5 will contain an implementation of what you've described here (partial function application), called functional.partial. The original PEP suggested calling the function
    'curry' but that was rejected since what it does isn't currying.

  • Anonymous
    September 14, 2005
    My avid readers (all 3 of them) may remember my old post on functional programming in C#. Well, with...

  • Anonymous
    September 14, 2005
    My avid readers (all 3 of them) may remember my old post on functional programming in C#. Well, with...

  • Anonymous
    October 01, 2005
    The comment has been removed

  • Anonymous
    March 30, 2006
    Sriram Krishnan blogs about using the anonymous delegates in C# 2.0 to implement a form of currying in...

  • Anonymous
    May 29, 2006
    Euro Hotel Site

  • Anonymous
    May 29, 2006
    Kansas City hotels

  • Anonymous
    July 04, 2007
    In order to explain how the createDelegate function works in the last post , we have to understand JavaScript

  • Anonymous
    February 05, 2009
    关键字yield通常用于迭代器中，向IEnumerable对象提供值或者结束迭代。如：yieldreturnexpression; yieldbreak; var ...

  • Anonymous
    February 05, 2009
    关键字 yield 通常用于迭代器中，向IEnumerable对象提供值或者结束迭代。 如： yieldreturnexpression; y...

  • Anonymous
    April 02, 2009
    PingBack from http://nihilist.expert.ge/?p=28

  • Anonymous
    May 28, 2009
    PingBack from http://paidsurveyshub.info/story.php?title=sriram-krishnan-functional-programming-in-c-currying

  • Anonymous
    June 15, 2009
    PingBack from http://einternetmarketingtools.info/story.php?id=16256