*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?

## No comments:

## 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.