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

## No comments:

Post a Comment