我知道这是异端,但是我试图把这个例子从
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中甚至是有意义的,特别是关于其内在的缺乏懒惰？
解决方法
好的,这让我相信功能性编程通常是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> 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,A>(y,a));
}
})
);
return y.get();
}
//Test that it works
public static void main(String[] args) {
F<Pair<FunctionRef<Integer,Integer>,Integer> fib = new F<Pair<FunctionRef<Integer,Integer>() {
@Override
public Integer f(Pair<FunctionRef<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));
}
注意,当程序运行时,它只为每个值输出一次“计算纤维”！
