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?

Frida

Oh GOD the Y combinator. I purposely managed to avoid that section of our course,.. my brain's was SO'ing. x__x But +1, good question anyway. – Futtock

That's a fixed point combinator, but I'm not sure that it's actually the Y combinator. I'm curious too, let's see what somebody more knowledgeable says… – Dagny

Isn't the Y combinator used to implement recursion? Meaning, you can't use it to implement recursion – Jackjackadandy

@Lou Franco: Woops! Yep, that sounds right. Y would allow one to implement recursion in a language that does not inherently support it, so long as that language supports higher order functions. Defining Y recursively defeats its original purpose (although it's still useful in some scenarios). – Frida

Your definition looks just like the Haskell definition of the fix function: fix f = let x = f x in x. Source (haskell.org) – Jarvis

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.

Allodium

Answer 2

I’m not sure what your question is but I guess the reason that neither the Y combinator nor your solution are seen much in the wild is twofold:

1. anonymous recursive functions are really rare; in particular since C# doesn’t have great (read: none at all) support for tail recursion.

2. There’s a much easier (more readable for the uninitiated) way of defining pseudo-“anonymous” recursive lambdas in C#:

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

   Granted, this is not anonymous but it’s “close enough” for practical purposes.

Ellon

Even the Y-combinator as defined in Scheme isn't "anonymous"; you have to call the function SOMETHING in order to reference it within your method, and the Scheme explanation is pretty close to what happens here (define that fac exists, then create a lambda that uses fac and assign it to fac). – Allodium

@Keith: “you have to call the function SOMETHING in order to reference it” – You really don’t: Y(f => x => x == 0 ? 1 : x * f(x - 1))(5) == 120. This is fundamentally different from my example because it still works with immutable variables, i.e. when you cannot redefine the meaning of fac as I have done in my code. – Ellon

… but of course this “cheats” by binding the “anonymous” function to a paramater symbol (f) of the enclosing lambda. – Ellon

This definition, while simple, has a problem when making a copy, as explained here: blogs.msdn.com/b/wesdyer/archive/2007/02/02/… – Glide

Answer 3

Haskell Curry invented the Y combinator to define and use anonymous recursive functions in the untyped lambda calculus, defined as follows:
Y = λf·(λx·f (x x)) (λx·f (x x))

My definition defeats the original purpose of the Y combinator as it relys upon C#'s inherent support for defining recursive functions. It is, however, still useful in that it allows one to define anonymous recursive functions in C#.

Frida