WHY Java

Y in Java.

Y is a cute concept from lambda calculus. It's easy to define in Haskell.

y f = f (y f)
fact r 0 = 1
fact r n = n * r (n-1)
f = y fact

An execution of f 3 computes 3!:

f 3
  = y fact 3
  = fact (y fact) 3
  = 3 * y fact 2
  = 3 * fact (y fact) 2
  = 3 * 2 * y fact 1
  = 3 * 2 * fact (y fact) 1
  = 3 * 2 * 1 * y fact 0
  = 3 * 2 * 1 * 1

While showing this to Claudia I realized that I never coded Y in Java. It's interesting to see how long it is.

interface Fun { int go(int n); }
interface UntiedFun { int go(Fun f, int n); }

public class Rec {
  public static void main(String[] args) {
    System.out.println(f(10));
  }

  public static int fact(Fun f, int n) {
    if (n == 0) return 1;
    return n * f.go(n-1);
  }

  public static int Y(final UntiedFun f, int n) {
    return f.go(new Fun() {
      public int go(int n) { return Y(f, n); }
    }, n);
  }

  public static int f(int n) {
    return y(new UntiedFun() {
      public int go(Fun f, int n) {return fact(f, n);}
    }, n);
  }
}

Great stuff you can do with recursion. Which reminds me: Did you figure out the last puzzle?