dtonhofer
Functional Programming in Java, Second Edition: Chapter 8: Hard-to-understand "Memoizer" can be made easy-to-understand by adding an "intermediate step" explainer
I had real trouble understanding the “memoizer”, I suppose Java syntax does not help in thinking about what should be a one-liner in Lambda calculus.
But after a couple of hours of thinking, it occurred to me that the “memoizing” code is just the end result of four simple transformations of the non-memoized code.
Suggesting to extend the text to explain it that way.
Here they are, based on the book’s code with some renaming of methods and parameters to make them more meaningful (at least to me):
The code below does not come with runnable code, which I will post separately.
RodCuttingOptimizer.java
package chapter8.rodcutting.book;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.stream.IntStream;
class RodCuttingOptimizer {
private final Map<Integer, Integer> pricingMap;
public RodCuttingOptimizer(final Map<Integer, Integer> pricingMap) {
this.pricingMap = Collections.unmodifiableMap(pricingMap);
}
// STEP 0:
// The initial solution as per the book.
public int maxProfitNaive(final int length) {
final int profitIfNotCut = pricingMap.getOrDefault(length, 0);
// dual recursive call!
final int maxProfitIfCut = IntStream.rangeClosed(1, length / 2)
.map(left -> maxProfitNaive(left) + maxProfitNaive(length - left))
.max()
.orElse(0); // if there is no value because the original IntStream is empty, use 0
return Math.max(profitIfNotCut, maxProfitIfCut);
}
// STEP 1:
// As above, but indirect, with the recursive descent in
// maxProfitIndirectInner() calling the function passed as argument #1.
// In this case, the topmost function.
// The call basically means "go do your work and call me with a smaller length on recursive descent"
public int maxProfitIndirect(final int length) {
return maxProfitIndirectInner(this::maxProfitIndirect, length);
}
// STEP 2:
// As above, but we do not want the *topmost* function to
// be called on recursive descent, but instead *another function* that we create locally.
public int maxProfitIndirectDetachedFromTop(final int length) {
final Function<Integer, Integer> shimFunction = new Function<>() {
public Integer apply(final Integer length2) {
// "this" is exactly the "shimFunction"
return maxProfitIndirectInner(this, length2);
}
};
// kickstart the recursive descent
return shimFunction.apply(length);
}
// STEP 2 WHICH WE CAN'T HAVE
// We cannot write the above like this in Java as there is no way to
// put anything into the $MYSELF$ hole, we would need a "Y Combinator" for that (I think)
/*
public int maxProfitDoublyIndirect2(final int length) {
Function<Integer, Integer> shimFunction = (Integer input) -> maxProfitIndirectInner($MYSELF$, length);
return shimFunction.apply(length);
}
*/
// STEP 3:
// As above, but now we are memoizing with a HashMap local to the "shimFunction".
// Note that if stream processing actually parallelizes its processing, we are
// in trouble as the access to the HasMap is not synchronized. So beware!
public int maxProfitIndirectMemoizing(final int length) {
final Function<Integer, Integer> shimFunction = new Function<>() {
private final Map<Integer, Integer> store = new HashMap<>();
public Integer apply(final Integer length2) {
if (!store.containsKey(length2)) {
int value = maxProfitIndirectInner(this, length2);
store.put(length2, value);
}
return store.get(length2);
}
};
// kickstart the recursive descent
return shimFunction.apply(length);
}
// STEP 4:
// As per the book, we can "factor out" the memoizing shim function into an (inner) class.
// In the book, this is called maxProfit().
private static class Memoizer {
public static <T, R> R memoize(final BiFunction<Function<T, R>, T, R> innerFunction, final T input) {
// An anonymous class implementing an interface!
// Containing a cache ("store") as a Map<T,R>
Function<T, R> memoizedFunction = new Function<>() {
private final Map<T, R> store = new HashMap<>();
public R apply(final T input) {
if (!store.containsKey(input)) {
store.put(input, innerFunction.apply(this, input));
}
return store.get(input);
}
};
return memoizedFunction.apply(input);
}
}
public int maxProfitIndirectMemoizingUsingMemoizer(final int length) {
// https://docs.oracle.com/javase/8/docs/api/java/util/function/BiFunction.html
// BiFunction<Function<Integer, Integer>, Integer, Integer> biFunction = this::maxProfitIndirectInner;
return Memoizer.memoize(this::maxProfitIndirectInner, length);
}
// The method that uses the "indirect" function.
//
// In the book, it is called "computeMaxProfit()"
// and "indirect" is called "memoizedFunction" (which is not entirely true as this is not
// properly the memoized function)
//
// "maxProfitIndirectInner" can be mapped to a java.util.function.BiFunction
// that maps the following types and roles:
//
// ( <Function<Integer, Integer> , Integer ) -> Integer
//
// ( [the "indirect function"] , [rod length] ) -> [max profit]
//
// In ML notation this would be simpler:
//
// ( Integer -> Integer ) -> Integer -> Integer
//
// This function is only "not static" in this example because its context (i.e. "this")
// contains the "pricingMap", which could also be passed as a separate parameter instead.
private int maxProfitIndirectInner(final Function<Integer, Integer> indirect, final int length) {
final int profitIfNotCut = pricingMap.getOrDefault(length, 0);
// dual recursive call!
final int maxProfitIfCut = IntStream.rangeClosed(1, length / 2)
.map(left -> indirect.apply(left) + indirect.apply(length - left))
.max()
.orElse(0); // if there is no value because the original IntStream is empty, use 0
return Math.max(profitIfNotCut, maxProfitIfCut);
}
}
Popular Pragmatic Bookshelf topics
As per the title, thanks.
New
Running the examples in chapter 5 c under pytest 5.4.1 causes an AttributeError: ‘module’ object has no attribute ‘config’.
In particula...
New
Hello! Thanks for the great book.
I was attempting the Trie (chap 17) exercises and for number 4 the solution provided for the autocorre...
New
@noelrappin
Running the webpack dev server, I receive the following warning:
ERROR in tsconfig.json
TS18003: No inputs were found in c...
New
Hi, I have just acquired Michael Fazio’s “Kotlin and Android Development” to learn about game programming for Android. I have a game in p...
New
The test is as follows:
Scenario: Intersecting a scaled sphere with a ray
Given r ← ray(point(0, 0, -5), vector(0, 0, 1))
And s ← sphere...
New
The markup used to display the uploaded image results in a Phoenix.LiveView.HTMLTokenizer.ParseError error.
lib/pento_web/live/product_l...
New
The allprojects block listed on page 245 produces the following error when syncing gradle:
“org.gradle.api.GradleScriptException: A prob...
New
Skimming ahead, much of the following is explained in Chapter 3, but new readers (like me!) will hit a roadblock in Chapter 2 with their ...
New
Getting an error when installing the dependencies at the start of this chapter:
could not compile dependency :exla, "mix compile" failed...
New
Other popular topics
Free and open source software is the default choice for the technologies that run our world, and it’s built and maintained by people like...
New
Learn from the award-winning programming series that inspired the Elixir language, and go on a step-by-step journey through the most impo...
New
You might be thinking we should just ask who’s not using VSCode :joy: however there are some new additions in the space that might give V...
New
poll
poll
Be sure to check out @Dusty’s article posted here: An Introduction to Alternative Keyboard Layouts It’s one of the best write-...
New
Oh just spent so much time on this to discover now that RancherOS is in end of life but Rancher is refusing to mark the Github repo as su...
New
Saw this on TikTok of all places! :lol:
Anyone heard of them before?
Lite:
New
Author Spotlight
Dmitry Zinoviev
@aqsaqal
Today we’re putting our spotlight on Dmitry Zinoviev, author of Data Science Essentials in ...
New
Author Spotlight:
Bruce Tate
@redrapids
Programming languages always emerge out of need, and if that’s not always true, they’re defin...
New
I’m able to do the “artistic” part of game-development; character designing/modeling, music, environment modeling, etc.
However, I don’t...
New
Explore the power of Ash Framework by modeling and building the domain for a real-world web application.
Rebecca Le @sevenseacat and ...
New
Categories:
Sub Categories:
Popular Portals
- /elixir
- /rust
- /wasm
- /ruby
- /erlang
- /phoenix
- /keyboards
- /python
- /js
- /rails
- /security
- /go
- /swift
- /vim
- /clojure
- /java
- /emacs
- /haskell
- /svelte
- /typescript
- /onivim
- /kotlin
- /c-plus-plus
- /crystal
- /tailwind
- /react
- /gleam
- /ocaml
- /elm
- /flutter
- /vscode
- /ash
- /html
- /opensuse
- /deepseek
- /zig
- /centos
- /php
- /scala
- /react-native
- /lisp
- /sublime-text
- /textmate
- /nixos
- /debian
- /agda
- /django
- /deno
- /kubuntu
- /arch-linux
- /nodejs
- /ubuntu
- /spring
- /revery
- /manjaro
- /julia
- /lua
- /diversity
- /markdown
- /quarkus









