Issue of the day: If you're using purely Java (or heaven forbid, C++), how do you *generically* memoize/cache values for functions that make recursive function calls? Reflection or runtime-method dispatch is probably pretty messy. It seems an actual Y-Combinator is *great* for this.

YCMemoizer.java

package memoizer;

import memoizer.ConcurrentLRUCache;

class YCMemoizer {
  interface F<R, A> { 
    R apply(A n); 
  }

  interface F_F<R, A> { 
    F<R, A> apply(F<R, A> f); 
  };

  interface FF_F<R, A> { 
    F<R, A> apply(FF_F<R, A> x); 
  }

  interface F_F_F<R, A> { 
    F<R, A> apply(F_F<R, A> g);
  };

  public class YC<R, A> implements F<R, A> {
    final private F_F_F<R, A> mF_F_F;
    final private F_F<R, A> mGenerator; 
    final private ConcurrentLRUCache mCache;
    
    @SuppressWarnings("unchecked")
    public YC(F_F<R, A> generator, final int cacheSize) {
      this.mGenerator = generator; 
      this.mCache = new ConcurrentLRUCache(cacheSize);
      this.mF_F_F = 
        new F_F_F<R, A>() { 
        public F<R, A> apply(final F_F<R, A> g) {
          return (new FF_F<R, A>() {
              public F<R, A> apply(final FF_F<R, A> f) {
                return f.apply(f); 
              }}).apply(new FF_F<R, A>() { 
                  public F<R, A> apply(final FF_F<R, A> f) {
                    return g.apply(new F<R, A>() { 
                        public R apply(A x) {
                          if (mCache.get(x) != null) {
                            return (R)(mCache.get(x)); 
                          } else {
                            R ans = f.apply(f).apply(x); 
                            mCache.put(x, ans);
                            return ans;
                          }
                        }});
                  }});
        }};
    }
    
    public R apply(A n) {
      return this.mF_F_F.apply(mGenerator).apply(n);
    }
  }

  public static void main(String args[]) {
    F_F<Long, Integer> generator = 
      new F_F<Long, Integer>() { 
      public F<Long, Integer> apply(final F<Long, Integer> f) {
        return new F<Long, Integer>() { 
          public Long apply(Integer n) {
            if (n < 2) return new Long(n);
            else return f.apply(n-1) + f.apply(n-2); 
          }};
      }};
    F<Long, Integer> YC = new YC<Long, Integer>(generator, 100);
    for (int i = 0; i < 60; ++i) {
      System.out.println(i);
      System.out.println(YC.apply(i));
      System.out.println("\n");
    }
  }
}