Fun with recursive Lambda functions
This post was originally published here.
I saw a couple of posts on recursive lambda expressions, and I thought it would be fun to write a class to encapsulate those two approaches. BTW, I’m running this on Orcas Beta 1, so don’t try this at home (VS 2005) kids. Let’s say I wanted to write a single Func variable that computed the factorial of a number:
Func<int, int> fac = x => x == 0 ? 1 : x * fac(x-1);
When I try to compile this, I get a compiler error:
Use of unassigned local variable 'fac'
That’s no good. The C# compiler always evaluates the right hand expression first, and it can’t use a variable before it is assigned.
Something of a solution
Well, the C# compiler couldn’t automagically figure out my recursion, but I can see why. So I have a couple of different solutions, one where I create an instance of a class that encapsulates my recursion, and another where a static factory method gives me a delegate to call. I combined both approaches into one class:
public class RecursiveFunc<T>
{
private delegate Func<A, R> Recursive<A, R>(Recursive<A, R> r);
private readonly Func<Func<T, T>, Func<T, T>> f;
public RecursiveFunc(Func<Func<T, T>, Func<T, T>> higherOrderFunction)
{
f = higherOrderFunction;
}
private Func<T, T> Fix(Func<Func<T, T>, Func<T, T>> f)
{
return t => f(Fix(f))(t);
}
public T Execute(T value)
{
return Fix(f)(value);
}
public static Func<T, T> CreateFixedPointCombinator(Func<Func<T, T>, Func<T, T>> f)
{
Recursive<T, T> rec = r => a => f(r(r))(a);
return rec(rec);
}
}
Using an instance of a class
The idea behind using a class is it might be more clear to the user to have an instance of a concrete type, and call methods on that type instead of calling a delegate directly. Let’s look at an example of this usage, with the Fibonacci and factorial recursive methods:
[TestMethod]
public void RecursiveFunc_WithFactorial_ComputesCorrectly()
{
var factorial = new RecursiveFunc<int>(fac => x => x == 0 ? 1 : x * fac(x - 1));
Assert.AreEqual(1, factorial.Execute(1));
Assert.AreEqual(6, factorial.Execute(3));
Assert.AreEqual(120, factorial.Execute(5));
}
[TestMethod]
public void RecursiveFunc_WithFibonacci_ComputesCorrectly()
{
var fibonacci = new RecursiveFunc<int>(fib => x =>
(x == 0) || (x == 1) ? x : fib(x - 1) + fib(x - 2)
);
Assert.AreEqual(0, fibonacci.Execute(0));
Assert.AreEqual(1, fibonacci.Execute(1));
Assert.AreEqual(1, fibonacci.Execute(2));
Assert.AreEqual(2, fibonacci.Execute(3));
Assert.AreEqual(5, fibonacci.Execute(5));
Assert.AreEqual(55, fibonacci.Execute(10));
}
So in each case I can pass in the Func delegate I was trying to create (without success) in the compiler error example at the top of the post. I instantiate the class with my recursive function, and call Execute to execute that function recursively. Not too shabby.
Using a static factory method
With a static factory method, calling the recursive function looks a little prettier. Again, here are two examples that use the Fibonacci sequence and factorials for recursive algorithms:
[TestMethod]
public void FixedPointCombinator_WithFactorial_ComputesCorrectly()
{
var factorial = RecursiveFunc<int>.CreateFixedPointCombinator(fac => x => x == 0 ? 1 : x * fac(x - 1));
Assert.AreEqual(1, factorial(1));
Assert.AreEqual(6, factorial(3));
Assert.AreEqual(120, factorial(5));
}
[TestMethod]
public void FixedPointCombinator_WithFibonacci_ComputesCorrectly()
{
var fibonacci = RecursiveFunc<int>.CreateFixedPointCombinator(fib => x =>
(x == 0) || (x == 1) ? x : fib(x - 1) + fib(x - 2)
);
Assert.AreEqual(0, fibonacci(0));
Assert.AreEqual(1, fibonacci(1));
Assert.AreEqual(1, fibonacci(2));
Assert.AreEqual(2, fibonacci(3));
Assert.AreEqual(5, fibonacci(5));
Assert.AreEqual(55, fibonacci(10));
}
After some thought on both, I think I like the second way better. Calling the Func delegate directly seems to look a little nicer, and it saves me from having to have some random Fibonacci or factorial helper class. Of course, I could still have those helper methods somewhere, but where’s the fun in that? Now if only I had taken a lambda calculus class in college…