Functional Programming in Java Part 3

Function0.java

package functions;

public abstract class Function0<R> {
    private R value = null;

    /**
     * The get() method should be synchronized, to ensure that we don't call
     * evaluate unnecessarily in a multithreaded setting.
     *
     * @return the result of evaluating -- results will be cached
     */
    public final synchronized R get() {
        if (value == null) {
            value = evaluate();
        }
        return value;
    }

    protected abstract R evaluate();
}

Function1.java

public abstract class Function1<R, T1> {
    public abstract R evaluate(final T1 i1);

    public final Function0<R> apply(final T1 i1) {
        return new Function0<R>() {
            @Override
            protected R evaluate() {
                return Function1.this.evaluate(i1);
            }
        };
    }
}

Function1_with_self.java

public abstract class Function1<R, T1> {
    public abstract R evaluate(final Function1<R, T1> self, 
                               final T1 i1);

    public final Function0<R> apply(final T1 i1) {
        return new Function0<R>() {
            @Override
            protected R evaluate() {
                return Function1.this.evaluate(Function1.this, i1);
            }
        };
    }
}

MemoizationTest_1.java

import functions.Function1;
import functions.MemoizedFunction1;
import org.junit.Test;

import static org.junit.Assert.assertTrue;

public class MemoizationTest  {
    private final Function1<Integer, Integer> fib =
            new Function1<Integer, Integer>() {
        @Override
        public Integer evaluate(final Integer i1) {
            if (i1 == 0 || i1 == 1) return 1;
            return apply(i1 - 1).get() + apply(i1 - 2).get();
        }
    };

    final Function1<Integer, Integer> memoFib =
            new MemoizedFunction1<Integer, Integer>() {
        @Override
        public Integer evaluate(final Integer i1) {
            if (i1 == 0 || i1 == 1) return 1;
            return apply(i1 - 1).get() + apply(i1 - 2).get();
        }
    };

    @Test
    public void testUnmemoizedFibonacci() {
        long start = System.currentTimeMillis();
        fib.apply(40).get();
        long end = System.currentTimeMillis();
        assertTrue(end - start > 2000);
    }

    @Test
    public void testMemoizedFibonacci() {
        long start = System.currentTimeMillis();
        memoFib.apply(40).get();
        long end = System.currentTimeMillis();
        assertTrue(end - start < 100);
    }
}

MemoizationTest_2.java

public class MemoizationTest  {

    /* ... Previous definition of fib and memoFib ... */

    @Test
    public void testRuntimeMemoization() {
        long start = System.currentTimeMillis();
        MemoizationUtils.memoize(fib).apply(40).get();
        long end = System.currentTimeMillis();
        assertTrue(end - start < 100);
    }
}

MemoizationTest_with_self.java

public class MemoizationTest  {
    private final Function1<Integer, Integer> fib =
            new Function1<Integer, Integer>() {
        @Override
        public Integer evaluate(final Function1<Integer, Integer> self,
                                final Integer i1) {
            if (i1 == 0 || i1 == 1) return 1;
            return self.apply(i1 - 1).get() 
                 + self.apply(i1 - 2).get();
        }
    };
    
    /* ... test methods unchanged -- memoFib also uses self.apply ... */
}

MemoizationUtils_1.java

public class MemoizationUtils {

    public static <R, T1> MemoizedFunction1<R, T1> memoize(Function1<R, T1> f) {
        return new MemoizedFunction1<R, T1> (){
            @Override
            public R evaluate(final T1 i1) {
                return f.evaluate(i1);
            }
        };
    }
}

MemoizationUtils_2.java

public class MemoizationUtils {

    public static <R, T1> MemoizedFunction1<R, T1> memoize(Function1<R, T1> f) {
        return new MemoizedFunction1<R, T1> (){
            @Override
            public R evaluate(final Function1<R, T1> self, final T1 i1) {
                return f.evaluate(this, i1);
            }
        };
    }
}

MemoizedFunction1.java

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

public abstract class MemoizedFunction1<R, T> extends Function1<R, T> {
    private final Map<T, Function0<R>> memoizedValues =
            new HashMap<T, Function0<R>>();

    @Override
    public synchronized Function0<R> apply(final T i1) {
        if (!memoizedValues.containsKey(i1)) {
            memoizedValues.put(i1, super.apply(i1));
        }
        return memoizedValues.get(i1);
    }
}

MemoizedFunction2and3.java

public abstract class MemoizedFunction2<R, T1, T2>
        extends Function2<R, T1, T2> {
    private final Function1<Function1<R, T2>, T1> memoizedCurry =
            new MemoizedFunction1<Function1<R, T2>, T1>() {
        @Override
        public Function1<R, T2> 
               evaluate(final Function1<Function1<R, T2>, T1> self,
                                         final T1 i1) {
            return new MemoizedFunction1<R, T2>() {
                @Override
                public R evaluate(final Function1<R, T2> self, final T2 i2) {
                  return MemoizedFunction2.this.evaluate(i1, i2);
                }
            };
        }
    };
    @Override
    public Function1<Function1<R, T2>, T1> curry() {
        return memoizedCurry;
    }
}

public abstract class MemoizedFunction3<R, T1, T2, T3>
        extends Function3<R, T1, T2, T3> {
    private final Function1<Function2<R, T2, T3>, T1> memoizedCurry =
            new MemoizedFunction1<Function2<R, T2, T3>, T1>() {
                @Override
                public Function2<R, T2, T3>
                       evaluate(final Function1<Function2<R, T2, T3>, T1> self,
                                                     final T1 i1) {
                    return new MemoizedFunction2<R, T2, T3>() {
                        @Override
                        public R evaluate(final Function2<R, T2, T3> self,
                                          final T2 i2, final T3 i3) {
                            return MemoizedFunction3.this.evaluate(i1, i2, i3);
                        }
                    };
                }
            };

    @Override
    public Function1<Function2<R, T2, T3>, T1> curry() {
        return memoizedCurry;
    }
}