Mmm, Curry

A recent comment asked why Haskell programmers sometimes write C# lambdas in this style:

Func<int, Func<int, int>> add = x=>y=>x+y;

which is then invoked as

sum = add(2)(3);

because of course the first invocation returns a function that adds two, which is then invoked with three. Why do that instead of the more straightforward

Func<int, int, int> add = (x,y)=>x+y;

and invoke it as

sum = add(2,3);

???

I was going to write a short article on that when I remembered that Wes already had done a better job at it than I likely would. Read this first before you read on.

Welcome back. I would add to that two interesting facts.

First, that the operation of rewriting an n-parameter function as a bunch of single-parameter functions to achieve “partial application” is called “currying” in honor of Haskell Curry, the logician after whom the programming languages Haskell and Curry are named.

And second, that it is a little-known fact that there is an ugly but sometimes useful way to “curry away” the first parameter of an existing function using reflection.

For example, suppose you've got

public class C {
public static int M(T t, int x) { whatever }
}

In C#, to curry away the first parameter you could simply say

T t = something;
Func<int, int> d = x=>C.M(t, x);

Which is of course a syntactic sugar for creating a hidden nested class with a field t and a method that takes an int, blah blah blah, lots of boring code spit out to do that.

If you need to curry away the first parameter of a method and are using some managed language that does not have anonymous functions, or you are writing a compiler but you don’t feel like spitting a whole bunch of helper methods like the C# compiler does, you can also do this directly with reflection:

T t = something;
MethodInfo methodInfo = typeof(C).GetMethod("M", BindingFlags.Static | BindingFlags.Public);
Func<int, int> d = (Func<int, int>) Delegate.CreateDelegate(typeof(Func<int, int>), t, methodInfo);

This works in the .NET framework 2.0 release or higher, and, unfortunately, requires that T be a reference type.

Notice that this kind of currying is essentially the same currying that happens when you make an extension method into a delegate. If static method C.M is an extension method extending type T then in C# you can say

Func<int, int> d = t.M;

and we essentially curry away the first argument to the extension method when creating the delegate, using tricks similar to the reflection trick. (We pass the managed address of the extension method to a constructor rather than passing the method info to the factory, but, basically its the same thing behind the scenes.) If you try this on an extension of a value type, you'll get an error. Sree has just posted an analysis of why this has to be a reference type.

Comments

• Anonymous
  June 25, 2009
  ...except when T in your last example is a value type, in which case it fails with an Argument Exception: "Error binding to target method," as discussed at http://stackoverflow.com/questions/1016033/extension-methods-defined-on-value-types-cannot-be-used-to-create-delegates-why. Excellent point; I had forgotten about that. I've updated the text. -- Eric

• Anonymous
  June 25, 2009
  Really nice trick, now with extension methods it makes sense to reuse delegate _target field for  the first parameter, pretending  it's the target object of an instance method. But the really amazing thing is that you release this in 2004/5, when extension methods didn't exist. Looks like you have an advicer from the future telling you what to do next :) Nice job

• Anonymous
  June 25, 2009
  Apparently currying was discovered by Moses Schoenfinkel in 1924, according to http://c2.com/cgi/wiki?CurryingSchonfinkelling Indeed. It often happens in mathematics that the first discovery or invention of a concept is unappreciated and unknown, and only upon the second discovery does the idea gain currency. There are many examples of this; for example, Benford's Law (which I discussed some time ago in this blog) was originally discovered by Newcombe decades earlier. -- Eric 

• Anonymous
  June 25, 2009
  I thought that partial application and currying actually had different meanings, and that most people meant "partial application" when they said "currying". Is this not the case after all then? Indeed, I am speaking informally and imprecisely in this article. "Partial application" is the act of providing too-few arguments to a function so as to somehow get as the result a function of fewer parameters which, when called with the missing arguments, gives the result of calling the original function with all the given arguments. "Currying" is the operation of taking a method of multiple arguments and reorganizing it into several nested methods of a single argument each, so that partial application "starting from the left" can happen easily. The two operations are so naturally a part of the same process that it is easy to conflate them when speaking informally.

• Anonymous
  June 25, 2009
  The comment has been removed

• Anonymous
  June 25, 2009
  Hmm... I still don't see the "why" part :) Why do this at all? Maybe a more realistic example than "add two numbers in a really convoluted way" is needed :)

• Anonymous
  June 25, 2009
  > In C#, to curry away the first parameter you could simply say This is not currying, it's partial application. While related concepts they're not the same thing (and your initial link even made the difference between them, though it called partial application the more general concept when clearly it's the other way around). Currying is the action of turning a function of arity n into a sequence of n functions of arity 1. Partial application is the action of turning a function of arity n into a function of arity n-k (with k>0 and commonly 1) by fixing some of its parameters (usually from the front, but not necessarily). You don't curry parameters, you curry functions. So "curry away the first parameters" just doesn't make any sense, while "partially apply" does. See my reply to Jon's comment above. -- Eric

• Anonymous
  June 25, 2009
  Probabably variation on the same theme are my "adapters" created for "fun" - some adapters are adopted from the C++ (Bind1st...) , adapter ToPredicate converts Func<T, bool> to Predicate etc. Automatic translaton of my article (original is only in czech).  http://tinyurl.com/mgxlwb (warning: possible syntax  errors ( both C# and english) in the article are caused by the translation). using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace FunctionExtensions {    static class FuncExtension    {        public static Func<T1, R> Bind1St<T0, T1, R>(T0 bindValue, Func<T0, T1, R> originalFunc)        {            return (arg => originalFunc(bindValue, arg));        }        public static Func<T0, R> Bind2nd<T0, T1, R>(T1 bindValue, Func<T0, T1, R> originalFunc)        {            return (arg => originalFunc(arg, bindValue));        }        public static Func<T0, bool> Not<T0>(Func<T0, bool> originalFunc)        {            return (arg => !originalFunc(arg));        }        public static Func<T0, T1, bool> Not<T0, T1>(Func<T0, T1, bool> originalFunc)        {            return ((arg1, arg2) => !originalFunc(arg1, arg2));        }        public static Func<T0, T1, T2, bool> Not<T0, T1, T2>(Func<T0, T1, T2, bool> originalFunc)        {            return ((arg1, arg2, arg3) => !originalFunc(arg1, arg2, arg3));        }        public static Func<T0, T1, bool> And<T0, T1>(Func<T0, T1, bool> originalFunc, Func<T0, T1, bool> originalFunc2)        {            return ((arg1, arg2) => originalFunc(arg1, arg2) && originalFunc(arg1, arg2));        }        public static Func<T0, bool> And<T0>(Func<T0, bool> originalFunc, Func<T0, bool> originalFunc2)        {            return (arg1  => originalFunc(arg1) && originalFunc2(arg1));        }        public static Func<T0, T1, bool> Or<T0, T1>(Func<T0, T1, bool> originalFunc, Func<T0, T1, bool> originalFunc2)        {            return ((arg1, arg2) => originalFunc(arg1, arg2)  || originalFunc(arg1, arg2));        }        public static Func<T0, bool> Or<T0>(Func<T0, bool> originalFunc, Func<T0, bool> originalFunc2)        {            return (arg1 => originalFunc(arg1) || originalFunc2(arg1));        }        public static Predicate<T> ToPredicate<T>(Func<T, bool> originalFunc)        {            return arg => originalFunc(arg);        }    } }

• Anonymous
  June 26, 2009
  Hi Scott, My point wasn't that they inveted currification on 2004/5, in fact i think that, when they disigned delegates they weren't thinking in curryfication at all (an academic thing that didn't make a lot of sense in a pre-Linq practical C# language): Instead they thought that an instance method shouldn't have a different signature than a static one, even if theres an extra parameter (the instance to call), so they hide it and now you can do: Func<int, int> a = myObject.Method; Func<int,int> b = MyClass.Method; This is ok. The amazing thing though is that they realize that hiding the first parameter could be interesting EVEN it this is not the instance parameter. And then, a few years later Extension methods appear, just a compiler trick to use the first parameter pretending is an instance, and now the feature makes sense. How C#/CLR guys know that this will happend? The CLR guys knew that people wanted to implement functional languages on the .NET framework. Consider the problem of using existing methods in a language that emphasizes partial application everywhere. If you are writing new functions, of course you can always curry them to make partial application easier. But if you want to partially apply existing framework methods, then it is helpful to compiler writers to have a way to do that via delegates. It's even nicer if the technique is "baked in" to the framework. That this happened to mesh very nicely with extension methods was a happy accident; my understanding is that their intention was to make it easier for third-party compiler writers. -- Eric