Haskell style memoization in Java

Question

I know this is heresy, but I tried to translate the examples from http://www.haskell.org/haskellwiki/Memoization to Java. So far I have:

public abstract class F<A,B> {
    public abstract B f(A a);
}

...
public static <A, B> F<A, B> memoize(final F<A, B> fn) {
  return new F<A, B>() {

    private final Map<A, B> map = new HashMap<A, B>();

    public B f(A a) {
      B b = map.get(a);
        if (b == null) {
          b = fn.f(a);
          map.put(a, b);
        }
      return b;
    }
  };
}

//usage:
private class Cell<X> {
    public X value = null;
}

...
final Cell<F<Integer, BigInteger>> fibCell = new Cell<F<Integer, BigInteger>>();
fibCell.value = memoize(new F<Integer, BigInteger>() {
  public BigInteger f(Integer a) {
     return a <= 1 ? BigInteger.valueOf(a) : fibCell.value.f(a - 1).add(fibCell.value.f(a - 2));
  }
});
System.out.println(fibCell.value.f(1000));

That works fine. Now I tried to implement the memoFix combinator defined as

memoFix :: ((a -> b) -> (a -> b)) -> a -> b
memoFix f =
   let mf = memoize (f mf) in mf

But I got stuck. Does this even make sense in Java, especially concerning its inherent lack of lazyness?

Answer 1

The Guava library actually implements something similar with its MapMaker:

final Map<Integer, String> memoizingMap = new MapMaker().makeComputingMap(
    new Function<Integer, String>() {
        @Override
        public String apply(final Integer input) {
            System.out.println("Calculating ...");
            return Integer.toHexString(input.intValue());
        }
    });
System.out.println(memoizingMap.get(1));
System.out.println(memoizingMap.get(100));
System.out.println(memoizingMap.get(100000));
System.out.println("The following should not calculate:");
System.out.println(memoizingMap.get(1));

Output:

Calculating ...
1
Calculating ...
64
Calculating ...
186a0
The following should not calculate:
1

The nice thing is that you can fine-tune the generated map for different aspects as expiration, concurrency level etc.

Answer 2

Okay, this has convinced me that functional programming is ususally a bad idea with Java. Lack of laziness can be worked around using a reference object (which essentially implements laziness). Here's a solution:

public static class FunctionRef<A, B> {
    private F<A, B> func;
    public void set(F<A, B> f) { func = f; }
    public F<A, B> get() { return func; }
}

public static class Pair<A, B> {
    public final A first; public final B second;
    public Pair(A a, B b) {
        this.first = a; this.second = b;
    }
}

public static <A, B> F<A, B> memoFix(final F<Pair<FunctionRef<A, B>, A>, B> func) {
    final FunctionRef<A, B> y = new FunctionRef<A, B>();
    y.set(
        memoize(new F<A, B>() {
            @Override
            public B f(A a) {
                return func.f(new Pair<FunctionRef<A, B>, A>(y, a));
            }
        })
    );
    return y.get();
}


//Test that it works
public static void main(String[] args) {
    F<Pair<FunctionRef<Integer, Integer>,Integer>, Integer> fib = new F<Pair<FunctionRef<Integer, Integer>,Integer>, Integer>() {
        @Override
        public Integer f(Pair<FunctionRef<Integer, Integer>, Integer> a) {
            int value = a.second;
            System.out.println("computing fib of " + value);
            if (value == 0) return 0;
            if (value == 1) return 1;
            return a.first.get().f(value - 2) + a.first.get().f(value - 1);
        }
    };

    F<Integer, Integer> memoized = memoFix(fib);
    System.out.println(memoized.f(10));
}

Note that when the program is run, it only outputs "computing fib of" once for each value!