A bit of truly ridiculous java geekery

Yeah, yeah. Haven't posted in two months, blah blah blah.

And this isn't going to be a life update post either. Sorry. People who are not CS types (and this is much more academic CS than practical CS stuff) should just skip this post.

Now, I present some gloriously ridiculous, useless code, done primarily to show that I could do this in java, and do so in a typesafe manner.

package com.google.functional;

// this is an interface with just one method, apply()
import com.google.common.base.Function;

import junit.framework.TestCase;

public class YNot extends TestCase {
  public static interface Fii extends Function<Integer, Integer> {
  }
  public static interface Branch extends Function<Branch, Fii> {
  }

  // Look, it's an anonymous recursive function!
  public void testY() {
    assertEquals(720,
        new Function<Function<Fii, Fii>, Fii>() {
          public Fii apply(final Function<Fii, Fii> f) {
            return new Branch() {
              public Fii apply(final Branch x) {
                return f.apply(new Fii() {
                  public Integer apply(Integer y) {
                    return x.apply(x).apply(y);
                  }
                });
              }
            }.apply(new Branch() {
              public Fii apply(final Branch x) {
                return f.apply(new Fii() {
                  public Integer apply(Integer y) {
                    return x.apply(x).apply(y);
                  }
                });
              }
            });
          }
        }.apply(new Function<Fii, Fii>() {
          public Fii apply(final Fii f) {
            return new Fii() {
              public Integer apply(Integer i) {
                return (i <= 0) ? 1 : i * f.apply(i - 1);
              }
            };
          }
        }).apply(6).intValue());
  }
}

Well that was a bit interesting. Get you head around how it works, if you've never worked all the way through the Y combinator before. The relevant wikipedia article might be useful. The translation from scheme to java was fairly straightforward; the trick was getting all the types to work out properly.

But wait, there's more! That code there isn't really reuseable at all. What's really needed is a version that works with arbitrary types:

package com.google.functional;

import com.google.common.base.Function;

import junit.framework.TestCase;

public class YCFun extends TestCase {
  public static interface BranchType<F, T> extends
      Function<BranchType<F, T>, Function<F, T>> {
  }

  public static <F, T> Function<Function<Function<F, T>,
      Function<F, T>>, Function<F, T>> y() {
    return new Function<Function<Function<F, T>, Function<F, T>>,
        Function<F, T>>() {
      public Function<F, T> apply(
          final Function<Function<F, T>, Function<F, T>> f) {
        return new BranchType<F, T>() {
          public Function<F, T> apply(final BranchType<F, T> x) {
            return f.apply(new Function<F, T>() {
              public T apply(F y) {
                return x.apply(x).apply(y);
              }
            });
          }
        }.apply(new BranchType<F, T>() {
          public Function<F, T> apply(final BranchType<F, T> x) {
            return f.apply(new Function<F, T>() {
              public T apply(F y) {
                return x.apply(x).apply(y);
              }
            });
          }
        });
      }
    };
  }

  // To get proper type inference
  public static <F, T> Function<F, T> yapply(
      final Function<Function<F, T>, Function<F, T>> f) {
    return YCFun.<F, T> y().apply(f);
  }

  public void testFactorial() {
    Function<Integer, Integer> factorial =
        yapply(new Function<Function<Integer, Integer>,
            Function<Integer, Integer>>() {
          public Function<Integer, Integer> apply(
              final Function<Integer, Integer> f) {
            return new Function<Integer, Integer>() {
              public Integer apply(Integer i) {
                if (i <= 0) {
                  return 1;
                } else {
                  return f.apply(i - 1) * i;
                }
              }
            };
          }
        });
    assertEquals(720, factorial.apply(6).intValue());
  }
}

Oh, and for those of you worried that I'm giving away internal Google secrets by using the interface com.google.common.base.Function, that's already been open-sourced as part of the Google Collections Library.