Y-Combinator in C#

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();
        }
    }
}

Comments

  1. subodh says:

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

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

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

Speak Your Mind

*