Java中的Haskell风格memoization

Question

我知道这是异端邪说,但我试图将这些例子从http://www.haskell.org/haskellwiki/Memoization翻译成Java.到目前为止,我有:

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));

这很好.现在我尝试实现memoFix定义为的组合子

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

但是我被困住了.这在Java中是否有意义,特别是关于其固有的懒惰性？

Answer 1

该番石榴图书馆真正实现类似的东西与它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));

输出:

计算...
1
计算...
64
计算...
186a0
以下不应计算:
1

好处是你可以针对不同方面微调生成的映射,如到期,并发级别等.

Answer 2

好吧,这使我确信函数式编程对Java来说通常是个坏主意.使用引用对象(基本上实现懒惰)可以解决缺乏懒惰的问题.这是一个解决方案:

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));
}

注意,当程序运行时,它只为每个值输出一次"计算fib"!