Functional programming techniques - Java 8 in Action: Lambdas, Streams, and Functional-Style Programming - page 397

14.5. Miscellany
In this section we explore two subtleties of being functional and of having referential
transparency; one concerns efficiency and the other concerns returning the same result. These
are interesting issues, but we place them here because they're subtleties concerning side effects
rather than conceptually central. We also explore the idea of combinators—methods or
functions that take two or more functions and return another function; this idea has inspired
many of the additions to the Java 8 API.
14.5.1. Caching or memoization
Suppose you have a side-effect-free method computeNumberOfNodes(Range) that calculates
the number of nodes inside a given range in a network with a tree-like topology. Let's assume
the network never changes (that is, the structure is immutable), but calling the method
computeNumberOfNodes is expensive to calculate because the structure needs to be traversed
recursively. You may want to calculate the results over and over again. If you have referential
transparency, there's a clever way of avoiding this additional overhead. One standard solution to
this issue is memoization —adding a cache (for example, a HashMap) to the method as a
wrapper—when the wrapper is called. It first consults the cache to see if the (argument, result)
pair is already in the cache; if so, it can return the stored result immediately; otherwise, you call
computeNumberOfNodes, but before returning from the wrapper you store the new (argument,
result) pair in the cache. Strictly speaking, this is a nonpurely functional solution because it
mutates a data structure shared by multiple callers, but the wrapped version of the code is
referentially transparent.
In practice this would work as follows:
final Map<Range,Integer> numberOfNodes = new HashMap<>();
Integer computeNumberOfNodesUsingCache(Range range) {
Integer result = numberOfNodes.get(range);
if (result != null){
return result;
}
result = computeNumberOfNodes(range);
numberOfNodes.put(range, result);
return result;
}