For last few days, I was trying to use lambda feature of C# to implement Y-Combinator. After few trial and errors, I was able to implement it in C# 3.5. I’m currently posting the code here and in my next blog, I’ll explain how I derived it.

In this code, Y-Combinator function, is used to implement anonymous recursive-factorial function called ‘factorial’.

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace YCombinator { class Program { delegate Func RecursiveFunction(RecursiveFunction f); static void Main(string[] args) { Func, Func>, Func> Y = (f) => { RecursiveFunction function = (h) => { return (x) => { return f(h(h))(x); }; }; return function(function); }; Func factorial = Y(function=> { return x => { return x == 0 ? 1 : x * function(x - 1); }; }); Console.WriteLine(factorial(5)); Console.ReadLine(); } } }

8) wow……by the way, what is a y-combinator??

A Y-combinator or Fixed Point Combinator is an anonymous function which allow the definition and use of anonymous recursive functions without having to define function literals.

i.e. This allows for anonymous recursion.

Sorry to double post, however I wasn’t able to get your version working.

What I was able to get working was the following:

private delegate Func Recursive(Recursive r);

// Y Combinator

static Func Y(Func<Func, Func> f)

{

Recursive rec = r => a => f(r(r))(a);

return rec(rec);

}

Func fib = Y(f => n => n > 1 ? f(n – 1) + f(n – 2) : n);

Func fact = Y(f => n => n > 1 ? n * f(n – 1) : 1);

(Hoping that the comment box preserves the angle brackets)

gah, it’s stripped out some of the angle brackets.