Functional Programming in C# – Currying


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 (33)

  1. check this out as this is very useful implementation

  2. vishnu vyas says:

    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 😀

  3. Roshan says:

    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. 🙂

  4. kfarmer says:

    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.

  5. sriram says:

    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

  6. sriram says:

    And Vishnu – if you strip out the comments, my implementation is 5 lines of code. Not bad in comparison to Paul Graham’s 3-4 lines 😉

  7. vishnu vyas says:

    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.

  8. vishnu vyas says:

    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?

  9. sriram says:

    Vishnu – I see that someone has been doing a lot of reading of Paul Graham.:-) I’ve heard this "catch-up-with-the-60s" arguments several times in the past (most of them in PG’s writings).

    To rebut your rebuttal :-), your Scheme code is squashed into one line – where in reality, it would be written like this (with line breaks – hope it comes out in the comment)

    (define (curry-adder x)

    (lambda(z)(+ x z)))

    If you compare with the lines of code it took for me, there is no big difference at all. I didn’t have to reinvent *lambda* – that is already there thanks to anonymous methods in C#. I had to implement ‘curry’.

    And one major point you’re missing with regards to C# vs Common Lisp – C# is a mainstream language with probably millions of programmers most if not all of whom have never seen lambda or functional stuff before. What anonymous delegates does is to get closures and lambda-goodness into the mainstream.

    Now, people will argue that it was already there in JScript but that’s an argument for another day.:-)

    And as Don Box said when he linked to this post – ‘Look for the C# 3.0 version in September’ 🙂

    As for catching up with the 1960s, don’t get me started on the cool stuff you can do with C# and .NET that you can’t do with Lisp 🙂

  10. Richard says:

    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.

  11. My avid readers (all 3 of them) may remember my old post on functional programming in C#. Well, with…

  12. My avid readers (all 3 of them) may remember my old post on functional programming in C#. Well, with…

  13. Jeswin P says:

    In case you want to achieve the same result without anonymous delegates, you will have to explicitly create the closure.

    I have a sample here: http://www.process64.com/CurryingInCWithoutAnonymousDelegates.aspx

    But I would not call either Currying in the true sense. I agree with Richard, partial function application is more correct.

  14. B# .NET Blog says:

    Sriram Krishnan blogs about using the anonymous delegates in C# 2.0 to implement a form of currying in…

  15. In order to explain how the createDelegate function works in the last post , we have to understand JavaScript

  16. Chagel says:

    关键字yield通常用于迭代器中,向IEnumerable对象提供值或者结束迭代。如:yieldreturnexpression;

    yieldbreak; var …

  17. 大 兵 says:

    关键字 yield 通常用于迭代器中,向IEnumerable对象提供值或者结束迭代。

    如:

    yieldreturnexpression;

    y…