Theory and Practice

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?

Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.

[フレーム]