Thursday, March 04, 2010

Combining Higher Order Functions in C#

Say I have a higher-order-function, ‘applier’, that takes another function and some arguments, applies the function to the arguments and returns the results multiplied by two:

Func<Func<int, int, int>, int, int, int> applier = (f, x, y) => f(x, y) * 2;

Now let’s say we have a function, ‘multiplier’ that simply multiplies two numbers:

Func<int, int, int> multiplier = (a, b) => a*b;

How can we combine applier and multiplier so that we end up with a function that simply multiplies two numbers and doubles the result?

First we curry applier:

var curried = Functional.Curry(applier);
 
So now ‘curried’ looks something like this:
 
Func<Func<int, int, int>, Func<int, Func<int, int>>> curried = f => x => y => f(x, y)*2;

It’s a function that takes a function and returns a function. So if we call it passing in ‘multiplier’ we should get back a function that does what we want:

var curriedCombined = curried(multiplier);

The only problem with ‘curriedCombined’ is that it’s in this curried form:

Func<int, Func<int, int>> curriedCombined = x => y => (x*y)*2;

So let’s DeCurry it (is there a better term for this?):

var combined = Functional.DeCurry(curriedCombined);

Now we have our target function. We can call it just like a normal delegate with two arguments:

Console.WriteLine("combined(4) = {0}", combined(4, 4));

Which outputs 32 as expected.

So now we have a nice mechanical way of turning higher-order-functions into normal functions by doing the following:

  1. Curry the higher-order-function
  2. Pass the function(s) that supply the function argument(s) into the curried version.
  3. DeCurry

All I have to do now is some serious reflection and I’ll have a working CurryFacility.

Here is my Functional class (stolen from Oliver Sturm)

using System;

namespace Mike.AdvancedWindsorTricks.Model
{
    public class Functional
    {
        public static Func<T1, Func<T2, T3>> Curry<T1, T2, T3>(Func<T1, T2, T3> function)
        {
            return a => b => function(a, b);
        }

        public static Func<T1, Func<T2, Func<T3, T4>>> Curry<T1, T2, T3, T4>(Func<T1, T2, T3, T4> function)
        {
            return a => b => c => function(a, b, c);
        }

        public static Func<T1, Func<T2, Func<T3, Func<T4, T5>>>> Curry<T1, T2, T3, T4, T5>(Func<T1, T2, T3, T4, T5> function)
        {
            return a => b => c => d => function(a, b, c, d);
        }

        public static Func<T1, T2, T3> DeCurry<T1, T2, T3>(Func<T1, Func<T2, T3>> function)
        {
            return (a, b) => function(a)(b);
        }

        public static Func<T1, T2, T3, T4> DeCurry<T1, T2, T3, T4>(Func<T1, Func<T2, Func<T3, T4>>> function)
        {
            return (a, b, c) => function(a)(b)(c);
        }

        public static Func<T1, T2, T3, T4, T5> DeCurry<T1, T2, T3, T4, T5>(Func<T1, Func<T2, Func<T3, Func<T4, T5>>>> function)
        {
            return (a, b, c, d) => function(a)(b)(c)(d);
        }
    }
}

3 comments:

Anonymous said...

Great stuff, thanks!

Congratulations on the oscar win for 'A Single Man' by the way!

smartcaveman said...
This comment has been removed by the author.
Anonymous said...

Apparently "uncurrying" is the dual concept of currying. See http://en.wikipedia.org/wiki/Currying