
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

Hello Brian,
I have some problems with running the code in your book. I like the style of the book very much and I have learnt a lot as...
New

The following is cross-posted from the original Ray Tracer Challenge forum, from a post by garfieldnate. I’m cross-posting it so that the...
New

Hi! I know not the intentions behind this narrative when called, on page XI:
mount() |> handle_event() |> render()
but the correc...
New

I am working on the “Your Turn” for chapter one and building out the restart button talked about on page 27. It recommends looking into ...
New

Title: Intuitive Python: docker run… denied error (page 2)
Attempted to run the docker command in both CLI and Powershell
PS C:\Users\r...
New

Title: Web Development with Clojure, Third Edition, vB17.0 (p9)
The create table guestbook syntax suggested doesn’t seem to be accepted ...
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 installing Cards as an editable package, I get the following error:
ERROR: File “setup.py” not found. Directory cannot be installe...
New

Book: Programming Phoenix LiveView, page 142 (157/378), file lib/pento_web/live/product_live/form_component.ex, in the function below:
d...
New

I am using Android Studio Chipmunk | 2021.2.1 Patch 2
Build #AI-212.5712.43.2112.8815526, built on July 10, 2022
Runtime version: 11.0....
New
Other popular topics

A thread that every forum needs!
Simply post a link to a track on YouTube (or SoundCloud or Vimeo amongst others!) on a separate line an...
New

Algorithms and data structures are much more than abstract concepts. Mastering them enables you to write code that runs faster and more e...
New

What chair do you have while working… and why?
Is there a ‘best’ type of chair or working position for developers?
New

Bought the Moonlander mechanical keyboard. Cherry Brown MX switches. Arms and wrists have been hurting enough that it’s time I did someth...
New
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

The V Programming Language
Simple language for building maintainable programs
V is already mentioned couple of times in the forum, but I...
New

Intensively researching Erlang books and additional resources on it, I have found that the topic of using Regular Expressions is either c...
New

Author Spotlight:
Peter Ullrich
@PJUllrich
Data is at the core of every business, but it is useless if nobody can access and analyze ...
New

If you’re getting errors like this:
psql: error: connection to server on socket “/tmp/.s.PGSQL.5432” failed: No such file or directory ...
New
Categories:
Sub Categories:
Popular Portals
- /elixir
- /rust
- /wasm
- /ruby
- /erlang
- /phoenix
- /keyboards
- /rails
- /js
- /python
- /security
- /go
- /swift
- /vim
- /clojure
- /emacs
- /haskell
- /java
- /onivim
- /typescript
- /svelte
- /crystal
- /kotlin
- /c-plus-plus
- /tailwind
- /gleam
- /react
- /ocaml
- /flutter
- /elm
- /vscode
- /ash
- /html
- /opensuse
- /centos
- /php
- /deepseek
- /zig
- /scala
- /sublime-text
- /textmate
- /lisp
- /nixos
- /debian
- /react-native
- /agda
- /kubuntu
- /arch-linux
- /django
- /revery
- /ubuntu
- /manjaro
- /spring
- /nodejs
- /diversity
- /lua
- /julia
- /c
- /slackware
- /neovim