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:

  1. Anonymous3:58 pm

    Great stuff, thanks!

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

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. Anonymous9:18 pm

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

    ReplyDelete

Note: only a member of this blog may post a comment.