dtonhofer

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);
    }

}

Where Next?

Popular Pragmatic Bookshelf topics Top

telemachus
Python Testing With Pytest - Chapter 2, warnings for “unregistered custom marks” While running the smoke tests in Chapter 2, I get these...
New
brianokken
Many tasks_proj/tests directories exist in chapters 2, 3, 5 that have tests that use the custom markers smoke and get, which are not decl...
New
herminiotorres
Hi! I know not the intentions behind this narrative when called, on page XI: mount() |&gt; handle_event() |&gt; render() but the correc...
New
joepstender
The generated iex result below should list products instead of product for the metadata. (page 67) iex&gt; product = %Product{} %Pento....
New
adamwoolhether
I’m not quite sure what’s going on here, but I’m unable to have to containers successfully complete the Readiness/Liveness checks. I’m im...
New
brunogirin
When trying to run tox in parallel as explained on page 151, I got the following error: tox: error: argument -p/–parallel: expected one...
New
taguniversalmachine
Hi, I am getting an error I cannot figure out on my test. I have what I think is the exact code from the book, other than I changed “us...
New
rainforest
Hi, I’ve got a question about the implementation of PubSub when using a Phoenix.Socket.Transport behaviour rather than channels. Before ...
New
SlowburnAZ
Getting an error when installing the dependencies at the start of this chapter: could not compile dependency :exla, "mix compile" failed...
New
dachristenson
I just bought this book to learn about Android development, and I’m already running into a major issue in Ch. 1, p. 20: “Update activity...
New

Other popular topics Top

ohm
Which, if any, games do you play? On what platform? I just bought (and completed) Minecraft Dungeons for my Nintendo Switch. Other than ...
New
AstonJ
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
PragmaticBookshelf
Rust is an exciting new programming language combining the power of C with memory safety, fearless concurrency, and productivity boosters...
New
dimitarvp
Small essay with thoughts on macOS vs. Linux: I know @Exadra37 is just waiting around the corner to scream at me “I TOLD YOU SO!!!” but I...
New
AstonJ
In case anyone else is wondering why Ruby 3 doesn’t show when you do asdf list-all ruby :man_facepalming: do this first: asdf plugin-upd...
New
Maartz
Hi folks, I don’t know if I saw this here but, here’s a new programming language, called Roc Reminds me a bit of Elm and thus Haskell. ...
New
PragmaticBookshelf
Author Spotlight Jamis Buck @jamis This month, we have the pleasure of spotlighting author Jamis Buck, who has written Mazes for Prog...
New
New
AstonJ
This is cool! DEEPSEEK-V3 ON M4 MAC: BLAZING FAST INFERENCE ON APPLE SILICON We just witnessed something incredible: the largest open-s...
New
mindriot
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

Latest in Functional Programming in Java, Second Edition

Functional Programming in Java, Second Edition Portal

Sub Categories: