Recursive lambda expressions in C# using YCombinator

In: C#| Functional Programming

17 Jun 2011

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.

2 Responses to Recursive lambda expressions in C# using YCombinator

Avatar

Project Euler – Problem 2 (Haskell vs C#) - JUSTINSHIELD.COM

June 19th, 2011 at 12:52 pm

[...] Here is another example of using the YCombinator => project-euler-problem-2-haskell-vs-c[...]

Avatar

Awadhendra

March 27th, 2012 at 6:11 am

Hi
Really you had written a very good article. Your way is very simple to explore your knowledge about lambda expression. I had also written a small blog on lambda expression that how to use lambda expression with use defined datatypes. I used lambda expression for finding records.

http://dabbu-csharphelp.blogspot.in/2012/03/lambda-expression.html

I hope this blog is also useful to those users who wants to know about lambda expressio that how to find records from list using lambda expression.

thanks to sharing this useful article.

Comment Form

About Justin

justin

Justin is a .NET Team Lead for Mammoth Brisbane. A Polyglot Developer proficient in multiple programming languages including [C#, C/C++, Java, Android, Ruby..]. He's currently taking an active interest in Teaching Kids to Code, Functional Programming, Robotics and 3D Printers.

About This Blog

Software Engineering is an art form, a tricky art form that takes as much raw talent as it does technical know how. I'll be posting articles on professional tips and tricks, dos and donts, and tutorials.

profile for Justin Shield on Stack Exchange, a network of free, community-driven Q&A sites

Photostream

  • Justin: Hi Alex, Thanks for the tip, I'll have to check out Xamarin Forms. I've been using MVVMCross a [...]
  • Alex Danvy: Hi, I would add 2 points : - Xamarin Forms allows to create shared code for (simple) UI. SHaring m [...]
  • Justin: Trog: This is off-topic to the point of the article. I'm using the term "software engineering" here [...]
  • trog: It should be noted that some fields will not hire a "software engineer" unless they are an actual, a [...]
  • Tonja: Nice work dude. [...]