Alternative Y combinator definition

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?

c# functional-programming y-combinator

Edit Report

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 Inva

answered 2011-01-21T23:55:16.193

Alternative Y combinator definition

1 Answer

Your Answer