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

johnp
Running the examples in chapter 5 c under pytest 5.4.1 causes an AttributeError: ‘module’ object has no attribute ‘config’. In particula...
New
jesse050717
Title: Web Development with Clojure, Third Edition, pg 116 Hi - I just started chapter 5 and I am stuck on page 116 while trying to star...
New
mikecargal
Title: Hands-On Rust (Chapter 11: prefab) Just played a couple of amulet-less games. With a bit of debugging, I believe that your can_p...
New
alanq
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
AndyDavis3416
@noelrappin Running the webpack dev server, I receive the following warning: ERROR in tsconfig.json TS18003: No inputs were found in c...
New
hazardco
On page 78 the following code appears: &lt;%= link_to ‘Destroy’, product, class: ‘hover:underline’, method: :delete, data: { confirm...
New
jonmac
The allprojects block listed on page 245 produces the following error when syncing gradle: “org.gradle.api.GradleScriptException: A prob...
New
EdBorn
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
dtonhofer
@parrt In the context of Chapter 4.3, the grammar Java.g4, meant to parse Java 6 compilation units, no longer passes ANTLR (currently 4....
New
dachristenson
I’ve got to the end of Ch. 11, and the app runs, with all tabs displaying what they should – at first. After switching around between St...
New

Other popular topics Top

DevotionGeo
I know that -t flag is used along with -i flag for getting an interactive shell. But I cannot digest what the man page for docker run com...
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
Exadra37
I am asking for any distro that only has the bare-bones to be able to get a shell in the server and then just install the packages as we ...
New
PragmaticBookshelf
Learn different ways of writing concurrent code in Elixir and increase your application's performance, without sacrificing scalability or...
New
AstonJ
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
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
DevotionGeo
I have always used antique keyboards like Cherry MX 1800 or Cherry MX 8100 and almost always have modified the switches in some way, like...
New
AnfaengerAlex
Hello, I’m a beginner in Android development and I’m facing an issue with my project setup. In my build.gradle.kts file, I have the foll...
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: