Lambda calculus can be summed up doing very much with very little, sacrificing only readability.

Personally i’ve found the inability to peform recusion with a lambda expression to be a little pain in what should be an elegant solution. Lets take a factorial for instance, how to write that as a lambda expression? The fathers of lambda calculus who invented lambda expressions in the 1930’s came up with a solution.

What is a lambda expression

A lambda expression simply put is an anonymous function that contains expressions or statements, it can be used to create delegates or expression tree types. All lambda expressions use the lambda operator =>, which reads ‘goes to’.

1

x => x * 2;

Would read, x goes to x times 2.

Lambda recursion using self replication and self application

The basics of getting a lambda expression to recurse upon itself uses self application. Take a function, that accepts a function and applies that to itself.

1

f => f(f);

For this situation we can’t really give it a Func<> type, so we define a special delegate.

1
2
3
4
5
6
7

delegate T Recursive<T>(Recursive<T> self);
 
// We can now apply the self application
Recursive<int> lambda = f => f(f);
 
// What happens if we do this
lambda(lambda);  // Infinite recursion.

This while not practical is useful in knowing that we can get a lambda to call iteself. Now all we need to do is make it useful.

Currying
Lamdas give us great syntax for creating delegates or little functions you can assign to a variable.

1
2

Func<int, int, int> add = (x, y) => x + y;
int a = add(3,4);  // a = 7

You can use the lambda syntax to build an add function that within it returns a function that is waiting for the other side of the add expression

1
2

Func<int, Func<int, int>> curriedAdd = x => y => x + y;
int b = curriedAdd(2)(3); // b = 5

The result is the same, aside from the syntax.

We can now curry the curriedAdd function by supplying one argument and then use our new add6 function as many times as we like.

1
2
3
4

var add6 = curriedAdd(6);
 
int c = add6(3);  // c = 9
int d = add6(5); // d = 11

Thankfully you don’t have to define your curried function when you’ve got a ‘Curry’ function to create it for you. Take an example that adds 4 things together.

1
2
3
4
5
6
7
8
9
10
11

Func<int, int, int, int, int> addFourThings = (a, b, c, d) => a + b + c + d;
 
var curriedAddFourThings = Curry(addFourThings);
 
int result = curriedAddFourThings(1)(2)(3)(4); // result = 10
 
var addOne = curriedAddFourThings(1);
var addOneTwo = addOne(2);
var addOneTwoThree = addOneTwo(3);
 
int result2 = addOneTwoThree(4); // result 2 = 10

Here is the set of Curry function overloads

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public Func<T1, Func<T2, T3>> Curry<T1, T2, T3>(Func<T1, T2, T3> function)
{
    return a => b => function(a, b);
}
 
public 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 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);
}

You may noticed that we’re going to be using currying for the next section.

Y combinator

Haskell Curry and Alan Turing both came up with ways to write lambda expressions that has the same self application and replication as lambda specified above. Their version however also replicates something else, the application of a given function (these have come to be known as Y-Combinators).

A Y-Combinator can be described roughly as “Give me myself and a higher order function f, and i’ll return a function that is a fixed point of f”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Program
{
	static void Main()
	{		
		Console.WriteLine(fact(6));
		Console.ReadKey();
	}
 
	delegate Func<T1, T2> Recursive<T1, T2>(Recursive<T1, T2> r);
 
	// The Y Combinator
	static Func<T1, T2> Y<T1, T2>(Func<Func<T1, T2>, Func<T1, T2>> f)
	{
		Recursive<T1, T2> rec = r => a => f(r(r))(a);
		return rec(rec);
	}
 
	// The Fixed Point Generator
	static Func<long, long> fact = Y<long, long>(f => n => n > 1 ? n * f(n - 1) : 1);
}

Note that we are passing in the lambda expression into the Y Combinator

So what’s actually occurring above?

First Y is a lambda expression, so there’s nothing to evaluate or execute.

1

 Y = y => f => x => f(y(y)(f))(x)

Next we evaluate the fixed point function (which I’ve actually summarised into the return statement of the Y Combinator).

1

 F = Y(Y) = f => x => f(Y(Y))(f))(x)

The higher order function F is a lambda so nothing to evaluate:

1

 F = fac => x => x > 1 ? x * fac(x - 1) : 1

Finally it gets to the lambda expression and then recurses through itself, because it’s defined as taking itself and an argument and applying it.

Now that you’re armed with the Y-Combinator see if you can do Project Euler – Problem 2 using the Y-Combinator. I’ll be posting my answer shortly.