Alternative Y combinator definition

Question

I've spent some time wrapping my head around the Y combinator lately, and I've found that it is usually defined (more or less) as follows (this is in C#, but the language of choice isn't important):

public delegate TResult SelfApplicable<TResult>(SelfApplicable<TResult> r);

public static TResult U<TResult>(SelfApplicable<TResult> r)
{
    return r(r);
}

public static Func<TArg1, TReturn> Y<TArg1, TReturn>(Func<Func<TArg1, TReturn>, Func<TArg1, TReturn>> f)
{
    return U<Func<TArg1, TReturn>>(r => arg1 => f(U(r))(arg1));
}

While that's perfectly functional (pun intended), it would seem that my definition is much simpler:

public static Func<TArg1, TReturn> Y<TArg1, TReturn>(Func<Func<TArg1, TReturn>, Func<TArg1, TReturn>> f)
{
    return f(n => Y(f)(n));
}

Is there any reason why the latter definition is not as common (I have yet to find it on the net)? Would it perhaps have something to do with defining Y in terms of itself?

Answer 1

Anonymous recursion, i.e. with a fixed point combinator, is not often seen in imperative, strongly-typed languages, for the very simple reason that it is easier to name your [censored] function than to define an anonymous function that performs the same task. Also, OOA&D teaches us that code which has value in multiple places shouldn't be duplicated; it should be named and thus accessible from a common place. Lambdas are by their very nature a one-off; a way of specifying a few lines of very situation-specific code for use in a more general algorithm like looping constructs. Most recursive algorithms are things that have pretty general application (sorting, recursive series generation, etc), which generally lead to you making them more widely accessible.

Lambda calculus aside, in most programming languages an anonymous function F must exist before it can be used. That precludes the definition of a function in terms of itself. In some functional languages such as Erlang, the function F is defined using "overloads", where simpler functions are used as base cases for more complex ones:

Fact(0) -> 1

Fact(i) -> Fact(i-1) * i

This would be fine, except that in Erlang-world this is now a named function "Fact", and when calling that method the program will "fall" through the overloads until it finds the first one for which the parameter(s) match. There isn't an equivalent in C# to this exact construct because C# doesn't support choosing an overload based on value.

The trick is to somehow get a reference to the function that can be passed to the function. There are many ways, all of which require a pre-existing reference SOMEWHERE. If you can't refer to the function by name, then the type of the FP-combinator function is Func<Func<Func<Func<Func<.... Konrad's method is the easiest, but in C# it ends up kind of a hack (it compiles but ReSharper still complains that it's a possible InvalidOperationException; can't invoke a null method pointer).

Here's something I use for simple cases, basically using the delegate workaround for not being able to implicitly type an implicitly-typed lambda:

public static class YCombinator
{
    public delegate TOut RLambda<TIn, TOut>(RLambda<TIn, TOut> rLambda, TIn a);
    public static Func<T,T> Curry<T>(this RLambda<T,T> rLambda)
    {
        return a => rLambda(rLambda, a);
    }
}

//usage
var curriedLambda = YCombinator.Curry<int>((f, i) => i <= 0 ? 1 : f(f, i - 1)*i)
var shouldBe120 = curriedLambda(5);

You can declare a Curry<TIn, TOut> overload to handle cases where the input type isn't the output type, such as producing a list of the first N prime numbers; that function P can be recursively defined as the function which produces a list of all positive integers which are not divisible by any lesser prime number. The fixed point P(1) => 2 defines a base case from which a recursive algorithm can be defined (albeit not a very efficient one):

var curriedLambda =
            YCombinator.Curry<int, List<int>>(
                (p, i) => i == 1
                              ? new List<int>{2}
                              : p(p, i - 1)
                                    .Concat(new[]
                                                {
                                                    Enumerable.Range(p(p, i - 1)[i - 2],
                                                                     int.MaxValue - p(p, i - 1)[i - 2])
                                                        .First(x => p(p, i - 1).All(y => x%y != 0))
                                                }).ToList()
                );
        Assert.AreEqual(new []{2,3,5,7,11}, curriedLambda(5));

And thus the conundrum presents itself; though you certainly CAN define everything as a higher-order function, this prime-finder would be MUCH faster if defined imperatively instead of functionally. The main speedup is simply defining p(p,i-1) at each level so it isn't evaluated 3 times per recursion level. A smarter language designed to work functionally would do that for you.