Haskell style memoization in Java

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) {开发者_如何学Go
     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?

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.

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!

The memoFix solution by Joe K was really impressive :-)

For practical purposes, this seems to be the most elegant solution for recursive (and non-recursive) functions, as it avoids the need for some reference variable:

import java.util.HashMap;
import java.util.Map;

public abstract class MemoF<A,B> extends F<A,B> {

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

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

    public abstract B func(A a);
}

Now you have to implement func as usual, except that you never call it recursively, but call f instead:

F<Integer, BigInteger> memoFib = new MemoF<Integer, BigInteger>(){
    public BigInteger func(Integer a) {
        return a <= 1 ? BigInteger.valueOf(a) : f(a - 1).add(f(a - 2));
    }
};

System.out.println(memoFib.f(100));
//--> 354224848179261915075

Why are you stuck? It looks like you're done.

You've successfully memoized calls to a function using a Map.

Here is a snippet from my recent solution for the exact same problem:

private final static class MutableFunction<A, B> implements Function<A, B> {
    public Function<A, B> f;

    @Override
    public B apply(A argument) {
        return f.apply(argument);
    }
}

/**
* Computes the fixed point of function f.
* Only terminates successfully if f is non-strict (that is returns without calling its argument).
*/
public static <A, B, R extends Function<A,B>> R fix(final Function<? super Function<A, B>, ? extends R> f) {
    MutableFunction<A, B> mutable = new MutableFunction<A, B>();
    R result = f.apply(mutable);
    mutable.f = result;
    return result;
}

Memofix of f is just a fix(composition(memo, f)) then!