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
your book suggests to use Image.toByteData() to convert image to bytes, however I get the following error: "the getter ‘toByteData’ isn’t...
New
Hi @Margaret ,
On page VII the book tells us the example and snippets will be all using Elixir version 1.11
But on page 3 almost the en...
New
This isn’t directly about the book contents so maybe not the right forum…but in some of the code apps (e.g. turbo/06) it sends a TURBO_ST...
New
“The ProductLive.Index template calls a helper function, live_component/3, that in turn calls on the modal component. ”
Excerpt From: Br...
New
When I run the coverage example to report on missing lines, I get:
pytest --cov=cards --report=term-missing ch7
ERROR: usage: pytest [op...
New
Modern Front-End Development for Rails - application does not start after run bin/setup (page xviii)
After some hassle, I was able to finally run bin/setup, now I have started the rails server but I get this error message right when I vis...
New
Title: Agile Web Development with Rails 7: (page 70)
I am running windows 11 pro with rails 7.0.3 and ruby 3.1.2p20 (2022-04-12 revision...
New
When running the program in chapter 8, “Implementing Combat”, the printout Health before attack was never printed so I assumed something ...
New
@mfazio23
I’ve applied the changes from Chapter 5 of the book and everything builds correctly and runs. But, when I try to start a game,...
New
From page 13:
On Python 3.7, you can install the libraries with pip by running these commands inside a Python venv using Visual Studio ...
New
Other popular topics
Please tell us what is your preferred monitor setup for programming(not gaming) and why you have chosen it.
Does your monitor have eye p...
New
I’ve been hearing quite a lot of comments relating to the sound of a keyboard, with one of the most desirable of these called ‘thock’, he...
New
I ended up cancelling my Moonlander order as I think it’s just going to be a bit too bulky for me.
I think the Planck and the Preonic (o...
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
Continuing the discussion from Thinking about learning Crystal, let’s discuss - I was wondering which languages don’t GC - maybe we can c...
New
Was just curious to see if any were around, found this one:
I got 51/100:
Not sure if it was meant to buy I am sure at times the b...
New
Will Swifties’ war on AI fakes spark a deepfake porn reckoning?
New
A Brief Review of the Minisforum V3 AMD Tablet.
Update: I have created an awesome-minisforum-v3 GitHub repository to list information fo...
New
This is cool!
DEEPSEEK-V3 ON M4 MAC: BLAZING FAST INFERENCE ON APPLE SILICON
We just witnessed something incredible: the largest open-s...
New
Ok, well here are some thoughts and opinions on some of the ergonomic keyboards I have, I guess like mini review of each that I use enoug...
New
Categories:
Sub Categories:
Popular Portals
- /elixir
- /rust
- /wasm
- /ruby
- /erlang
- /phoenix
- /keyboards
- /python
- /js
- /rails
- /security
- /go
- /swift
- /vim
- /clojure
- /emacs
- /haskell
- /java
- /svelte
- /onivim
- /typescript
- /kotlin
- /crystal
- /c-plus-plus
- /tailwind
- /react
- /gleam
- /ocaml
- /flutter
- /elm
- /vscode
- /ash
- /html
- /opensuse
- /zig
- /centos
- /deepseek
- /php
- /scala
- /react-native
- /lisp
- /textmate
- /sublime-text
- /nixos
- /debian
- /agda
- /django
- /deno
- /kubuntu
- /arch-linux
- /nodejs
- /revery
- /ubuntu
- /manjaro
- /spring
- /diversity
- /lua
- /julia
- /markdown
- /c








