Rosetta Stone: Y-combinator

Question

The Y-combinator is defined as:

Y = λf. (λx. f (x x)) (λx. f (x x))

Using this combinator, you can write recursive lambda functions or intercept recursive methods with custom code.

How is the Y-combinator written in various languages?

I'd be interested in seeing the Y-combinator defined and used to implement a recursive factorial function. For example, in F#:

let rec y f x = f (y f) x
let factorial = y (fun f -> function 0 -> 1 | n -> n * f(n - 1))

Try to limit your responses to one-language, one answer.

Answer 1

Here's a single-argument Y-combinator in C#:

public static Func<T, U> YCombinator<T, U>(Func<Func<T, U>, Func<T, U>> f) {
  return yc => x => f(yc(yc)(f))(x);
}

Your factorial example would look like this:

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

---

This isn't the only way to do it, of course. Here's a much more comprehensive example.

Answer 2

PostScript

The Y combinator as a nameless function with no explicit variable bindings (squeezed to fit on one line :D):

{[{[exch{dup exec exec}aload pop]cvx exec}aload pop 10 9 roll exch]cvx dup exec}

Actually, this is the applicative-order Y combinator, adapted from Scheme.

As an example, here's how to use it to compute the factorial of a nonnegative integer:

%%% Read from stdin (input should be a nonnegative integer)
(%stdin) run

%%% Factorializer -- a function that takes a function as input;
%%% this computes the factorial by doing everything except the recursive step
%%% and then calling the input function as the recursive step
{[{dup 0 eq exch {1} exch [exch dup 1 sub exec mul} aload pop
[6 1 roll 16 15 roll 3 1 roll] cvx {aload pop] cvx ifelse} aload pop] cvx}

%%% Y combinator -- takes the factorializer as input and returns a function that
%%% computes the factorial of any nonnegative integer
{[{[exch {dup exec exec} aload pop] cvx exec} aload pop 10 9 roll exch]
cvx dup exec}

%%% Apply Y combinator to factorializer to produce factorial function;
%%% then apply factorial function to input number and print the result
exec exec =

Usage: $ echo 20 | gs -q -dNODISPLAY -dNOPROMPT -dBATCH thisfile.ps

Output: 2432902008176640000

No iterative looping constructs, no function names, not even local variable bindings.*

PostScript is the ultimate functional programming language.

*You can also use any of these in PostScript, but this nameless version is way cool.

Answer 3

R version based on The Little Schemer:

Y <- function (fun) (function (f) f(f))(function (f) fun(function (x) f(f)(x)))

Quick example:

factorial <- function (fun) (function (x) if (x < 2) 1 else x * fun(x - 1))
Y(factorial)(5)    # should return 120

Answer 4

Ruby version based on my R version:

def Y
  lambda {|f| f.call(f)}.call(lambda {|f| yield lambda {|x| f.call(f).call(x)}})
end

Example:

def factorial
  lambda {|x| x < 2 ? 1 : x * yield(x - 1)}
end

Y {|f| factorial &f}.call(5)    # should return 120

Answer 5

JavaScript version based on my R version; most of the verbosity comes from all the return keywords:

Y = function (fun) {
  return (function (f) {return f(f)})(function (f) {return fun(function (x) {return f(f)(x)})})
}

Example:

factorial = function (fun) {
  return function (x) {return x < 2 ? 1 : x * fun(x - 1)}
}

Y(factorial)(5)    # should return 120

---

JavaScript 1.8 (SpiderMonkey)

Strips out all the verbose return and makes it even more fun to read!

Y=function(fun)(function(f)f(f))(function(f)fun(function(x)f(f)(x)))
factorial=function(fun)function(x)x<2?1:x*fun(x-1);
Y(factorial)(5)

Answer 6

Lua

y = function (f) 
  local function g(h) return f (function (x) return (h(h))(x) end) end
  return g(g)
end

Example:

fac = function (f)
  return function (x) if x < 2 then return x else return x * f(x-1) end end 
end

=y(fac)(5) -- should print 120

Answer 7

Haskell

y f = f (y f)

With type

y :: (a -> a) -> a

Usage:

fact = y (\f n -> if n <= 1 then 1 else n * f (n - 1))

Answer 8

PHP 5.3

function Y($F) {
    $func =  function ($f) { return $f($f); };
    return $func(function ($f) use($F) {
        return $F(function ($x) use($f) {
            $ff = $f($f);
            return $ff($x);
        });
    });
 }

via http://php100.wordpress.com/tag/y-combinator/

Answer 9

Python (translated from Lua example above, still not completely sure how it works xD)

def y(f):
    def g(h):
        return f(lambda x: (h(h))(x))
    return g(g)

#factorial example
fact = y(lambda f: (lambda x: x if x < 2 else x * f(x-1)))

fact(5) # returns 120

Answer 10

Scala: (taken from here)

def Y[A, B](f: (A => B) => (A => B)) = {
  case class W(wf: W => A => B) {
    def apply(w: W) = wf(w) 
  }
  val g: W=>A=>B = w => f(w(w))(_)
  g(W(g))
}

Answer 11

This article shows how you can write a Y combinator in Java.

Answer 12

I had some trouble mapping some of these implementations to the Y-combinator definition given in the question. The obvious translation to Perl looped. Then I discovered, with the help of the Wikipedia article on fixed point combinators, that this definition assumes call-by-name or lazy evaluation. For call-by-value languages, such as Scheme, C, and Perl, you need an extra layer of lambda to make it work. The Wikipedia article calls this fixed point combinator Z.

Y = λf. (λx. f (x x)) (λx. f (x x))
Z = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))

Here is an implementation in Perl.

# Y-combinator, implemented as Z above since Perl is call by value.
$Y = sub { my ($f) = @_;
           # g is shorthand for the repeated lambda x function in Z
           my $g = sub { my ($x) = @_;
                         $f->(sub { my ($y) = @_;
                                    $x->($x)->($y) }) };
           $g->($g) };

# Factorial function for use with Y-combinator
$F = sub { my ($fact) = @_;
           sub { my ($n) = @_;
                 $n <= 0 ? 1 : $n * $fact->($n - 1) } };

printf "%d! => %d\n", 5, $Y->($F)->(5);

This isn't too hard to explain. The call $Y->($F) produces the factorial function, which comes from Y's call to $g passing itself as the argument, and inside $g, $x is bound to $g as well, so $x->($x) is the same as $g->($g) and $Y->($F). The factorial function comes from the lambda n returned by $F, with $fact properly bound. This result is also returned by $g inside $Y and then returned by $Y itself. Finally, how is $fact, referenced by the lambda n factorial function, properly bound? That is the lambda y, not the factorial function exactly, but one that uses $x->($x) to get factorial and returns the result of passing factorial whatever it is passed.