Do we need fixed point combinators in C#?

Question

I was playing with recursive lambdas in C# and have found two approaches to do this on the web. One approach uses fixed point combinator and the other does not. In the code below f1 is built using combinator, and f2 is defined directly. My question is, do we need fixed point combinators in C# or the language already provides all we need, so we can leave them alone?

class Program
{
    static Func<T, T> F<T>(Func<Func<T,T>,Func<T,T>> f)
    {
        return x => f(F(f))(x);
    }

    static void Main(string[] args)
    {
        Func<Func<int,int>,Func<int,int>> f = fac => x => x == 0 ? 1 : x * fac(x - 1);
        var f1 = F(f);

        Console.WriteLine(f1(5));

        Func<int, int> f2 = null;
        f2 = x => x == 0 ? 1 : x * f2(x - 1);

        Console.WriteLine(f2(5));
    }
}

Answer 1

As we can give a name to a method, that means that the language already has the necessary support for recursion built into it.

Note that the second method given in your question involves changing the value of a variable after it has been introduced, making it not "pure" functional programming. Y-combinator is only necessary if your system of functional calculus doesn't have a built-in notion of a function that can refer to its own definition by name before the definition is completely defined. C# has two ways to do that directly: 1. initially defining the function variable as null and 2. declaring an ordinary named method (by far the preferred technique).

Answer 2

Another alternative is to declare your recursive Func delegates as static members:

static Func<int, int> Factorial = (n) => n <= 1 ? 1 : n*Factorial(n - 1);

Answer 3

What does "need" mean? C# doesn't need them, as you shouldn't be attempting this sort of functional programming in C#. It's just a pathway to pain.

Memoizing a recursive function is one place you'd want a fixed point combinator. Compare this in C# to Haskell.

So, before C# "needs" this, it has a needs a lot of work to make this sort of programming reasonably practical.

Answer 4

I think it can be rather elegant with an extra utility class called Recursive as follows:

public static class Recursive {
            public static Func<R> Func<R>(
                Func<Func<R>, Func<R>> f) { 
                return () => f(Func(f))(); }
            public static Func<T1, R> Func<T1, R>(
                Func<Func<T1, R>, Func<T1, R>> f) { 
                return x => f(Func(f))(x); }
            public static Func<T1, T2, R> Func<T1, T2, R>(
                Func<Func<T1, T2, R>, Func<T1, T2, R>> f) {
                return (a1, a2) => f(Func(f))(a1, a2);
            }
            //And so on...
        }

class Program {

    static void Main(string[] args) {

        Console.WriteLine(
            Recursive.Func<int, int>(factorial =>
                x => x == 0 ? 1 : factorial(x - 1) * x
            ) 
            (10)
        );

        Console.WriteLine(
            Recursive.Func<int,int,int>(gcd =>
                (x,y) => 
                    x == 0 ? y:
                    y == 0 ? x:
                    x > y  ? gcd(x % y, y):
                    gcd(y % x, x)
            )
            (35,21)
        );
    }
}