What do we want to achieve?
When one works with the functional aspects of programming, one come across, at some point of time, the term of Memoizing. What is this supposed to be and how can we map this in Core Java?
In addition to the source text examples given in this article, I will also use the sources from the Open Source project
Functional-Reactive http://www.functional-reactive.org/. The sources are available at https://github.com/functional-reactive/functional-reactive-lib
Memoizing
It is said in functional programming that a function always returns the same output value for a particular input value. Exactly the same? Yes, the function is meant to return the same. If the return value is of the type int, then it is not a problem. But how does it look like, if the return value is an instance of the type Jelly baby?
Therefore, it must be noted here, what is the difference between same value and identical value.
Let us start with a simple example and use the following function.
private static Function<Integer, Integer> squareFunction = x -> {
System.out.println("In function");
return x * x;
};I am using System.out in this example to shown, how often the function has been called. Naturally, this is not meant for the productive use.
If this function is now called twice, then one can also see this on the screen. In action appears twice.
final Integer a = squareFunction.apply(2);
final Integer b = squareFunction.apply(2);We now define a method, in order to use the memoizing on a function.
Function<Integer, Integer> memoizationFunction =
Memoizer.memoize(squareFunction);The aim of this method is that if the function is returned thereafter with the same value when the call is made twice, the message is seen only once on the screen. In other words, the result is calculated only once. Therefore, the function should make a note that it has already produced this result once.
ConcurrentHashMap
One can make use of a map, in order to make a note of the values. Here, the calculated output values are kept for the respective input values. If a result is requested again, it is first seen in the map, whether a result is already present there. If yes, then this result is used; else, it is calculated and also stored in the map. ConcurrentHashMap is recommended as implementation of the map, because we cannot rule out that multiple accesses take place at the same time.
Since Java 8 there is the method computeIfAbsent, with which the key as well as also the calculation of the value can be specified as function. The implementation of the functionality Memoizing is now nothing else than an enveloping of the function.
private static Function<Integer, Integer> squareFunction = x -> {
System.out.println("In function");
return x * x;
};
public static class Memoizer<T,U> {
private final Map<T,U> memoizationCache
= new ConcurrentHashMap<>();
private Function<T, U> doMemoize(final Function<T,U> function) {
return input -> memoizationCache
.computeIfAbsent(input, function);
}
public static <T, U> Function<T, U>
memoize(final Function<T, U> function) {
return new Memoizer<T, U>().doMemoize(function);
}
}
public static void main(String[] args) {
final Function<Integer, Integer> f =
Memoizer.memoize(squareFunction);
final Integer a = f.apply(2);
final Integer b = f.apply(2);
}If one now uses the function, which has been returned from the call of the method memoize(..), then one notices that in case of a multiple use of the same input value, the message appears only once on the screen. We are now in a position to equip a function Function<A,B> with the features of memoizing. But how does it look like in case of a BiFunction<A,B,R>?
BiFunction
A BiFunction is a function with two input values. This means that a result value now depends upon two values. To this extent, everything is quite simple; but how do we now build the function Memoizing?
To do this, we play around a little with the BiFunction and try to transform it. For this, we use the following example function.
BiFunction<Integer,Integer,Integer> biFunctionA = (x,y) -> x * y;One can also transform this function in a function, which is built in two stages.
Function<Integer, Function<Integer, Integer>> biFunctionB
= x -> y -> x * y;The process is known as Currying. If you wish to read more theory about this, you can start with https://de.wikipedia.org/wiki/Currying
To implement memoizing now, one can now start with the variant shown earlier at the respective stage.
Function<Integer, Function<Integer,Integer>> memoizationFunction
= Memoizer.memoize(x -> Memoizer.memoize(y -> x * y));Therefore, the usage is now everything else but comfortable. The aim should be that a BiFunction is specified and a BiFunction is returned again with the features of memoizing. But one after the other.
create
The first step is the transformation from BiFunction<A,B,R> to a Function<A, Fuction<B,R>>. To do this, we define a method, which does exactly this transformation for us.
private static final BiFunction<Integer, Integer, Integer> biFunctionA = (x , y) -> x * y;
public static Function<Integer, Function<Integer, Integer>> create(
BiFunction<Integer, Integer, Integer> biFunction) {
return Memoizer.memoize(x -> Memoizer.memoize(y -> biFunction.apply(x , y)));
}
public static void main(String[] args) {
final Function<Integer, Function<Integer, Integer>> function = create(biFunctionA);
System.out.println("memoizationFunction = " + function.apply(2).apply(3));
System.out.println("memoizationFunction = " + function.apply(2).apply(3));
}transform
The first step is completed, now only the reverse transformation to a BiFunction remains. Here too, one can quite easily delegate the call.
public static BiFunction<Integer, Integer, Integer> transform(
Function<Integer, Function<Integer, Integer>> function) {
return (a,b) -> function.apply(a).apply(b);
}Both of them together result in the following method.
public static Function<Integer, Function<Integer, Integer>> create(
BiFunction<Integer, Integer, Integer> biFunction) {
return Memoizer.memoize(x -> Memoizer.memoize(y -> biFunction.apply(x , y)));
}
public static BiFunction<Integer, Integer, Integer> transform(
Function<Integer, Function<Integer, Integer>> function) {
return (a,b) -> function.apply(a).apply(b);
}
public static BiFunction<Integer, Integer, Integer> memoize(
BiFunction<Integer, Integer, Integer> f){
return transform(create(biFunctionA));
}Or when one transfers both into each other.
public static BiFunction<Integer, Integer, Integer> memoize(
BiFunction<Integer, Integer, Integer> f){
Function<Integer, Function<Integer, Integer>> cf
= Memoizer.memoize(x -> Memoizer.memoize(y -> f.apply(x , y)));
return (a,b) -> cf.apply(a).apply(b);
}Till now, we have referred everything to one specific function. One can formulate this in a generic way, thanks to Generics.
generic version
To do this, we define types A, B and R.
public static <A,B,R> BiFunction<A, B, R> memoize(BiFunction<A, B, R> f) {
Function<A, Function<B, R>> cf
= Memoizer.memoize(x -> Memoizer.memoize(y -> f.apply(x , y)));
return (a , b) -> cf.apply(a).apply(b);
}
public static void main(String[] args) {
Main.<Integer,Integer,Integer>memoize((x , y) -> x * y).apply(2 , 3);
Main.<String, String, Integer>memoize((x,y) -> Integer.valueOf(a) * Integer.valueOf(b));
}TriFunction to n-Function
If one has reached this point, one can also consider how it would look like with a TriFunction. Unfortunately, there is no TriFunction in JDK. But this should not discourage you, if you still need this function.
A TriFunction is defined quickly, if one takes the BiFunction from JDK as example, because it is very intuitive for the developer to use this.
@FunctionalInterface
public interface TriFunction<T1, T2,T3, R> {
R apply(T1 t1, T2 t2, T3 t3);
default <V> TriFunction<T1, T2,T3, V> andThen(Function<? super R, ? extends V> after) {
Objects.requireNonNull(after);
return (T1 t1, T2 t2, T3 t3) -> after.apply(apply(t1, t2, t3));
}
}One can take the same path here as in the case of BiFunction.
public static <A, B, C, R> TriFunction<A, B, C, R> memoize(TriFunction<A, B, C, R> f) {
Function<A, Function<B, Function<C,R>>> cf
= Memoizer.memoize(
x -> Memoizer.memoize(
y -> Memoizer.memoize(
z -> f.apply(x , y , z))));
return (a , b, c) -> cf.apply(a).apply(b).apply(c);
}
One can clearly see here that we can continue defining this till any
particular size. The path to NFunction is thus free.
And there was still the legacy code
One or the other developer is confronted time and again with somewhat older source code. In this case, it mostly happens that the conversion to new interfaces cannot mostly be mapped. But what can one do now, in order to take advantage from this kind of partial caching?
Let us have a look here at a classical piece of Java.
public static class MyLegacyClass {
public Value doWorkA(int a, int b){
return new Value();
}
public Value doWorkB(int a, int b){
return new Value();
}
}In order now to use these methods from an instance of the class MyLegacyClass, one can proceed as follows. A method reference is fetched to the method doWork of this instance. This method reference matches the signature of a BiFunction, because it has two parameters and one return value.
final MyLegacyClass myLegacyClass = new MyLegacyClass();
final BiFunction<Integer, Integer, Value> doWork = myLegacyClass::doWorkA;
final BiFunction<Integer, Integer, Value> memoize = Memoizer.memoize(doWork);
This BiFunction can now be equipped with the features of partial caching by means of memoizing. The original method remains unaffected by this and can continue to be used as before.
It how happens that the old source code also has methods with more than 2 parameters. One can then work here with the self-defined TriFunction.
Summary
We have seen here that sometimes it is quite easy to map generic patterns in Java. Similarly, we now have a bridge between the old and the new source code thanks to MethodHandles. Thus, there is a quite comfortable way to combine old source code without byte code manipulation or large factoring with our new concepts.
You can find the source code at:
https://github.com/Java-Publications/functional-reactive-with-core-java-007.git
If you have questions or comments, simply contact me at sven@vaadin.com or via Twitter @SvenRuppert.
Happy coding!