# Recursive lambda expressions in C# using YCombinator

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 Project Euler – Problem 2 (Haskell vs C#) - JUSTINSHIELD.COM

[…] Here is another example of using the YCombinator => project-euler-problem-2-haskell-vs-c[…] 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.  Justin is a Senior Software Engineer living in 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, 3D Printers, RC Quad-Copters and Augmented Reality.

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

• What I look for in a senior software engineer Justin Shield: […] I’m not going to list the design patterns that you’ll need, I’ve already [...]
• Justin: Hi Ross, I do actually like Umbraco, it provides some nice abilities for creating websites that I [...]
• Justin: Hi GordonBGood, Thanks for taking the time in replying. You're absolutely correct, it is turners s [...]
• Ross Gallagher: Hi Justin, I'm a fellow Aussi looking to use Umbraco to create a simple website. I have downloaded [...]
• GordonBGood: This is the "Turner Sieve" which **IS NOT** the Sieve of Eratosthenes (SoE) neither by algorithm nor [...]