Created
March 19, 2012 21:50
-
-
Save msfroh/2127395 to your computer and use it in GitHub Desktop.
Functional Programming in Java Part 3
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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(); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
}; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
}; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 ... */ | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
}; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
}; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment