home search about rss feed twitter ko-fi

One More Thing: Algebraic Substitution (Scala 3 Video)

Algebraic Substitution

Before we move on from this Word Count example I need to add one very important point: Because I wrote wc using only pure functions and immutable values, both you and a compiler are free to reduce this code.

What this means is that at the end of the previous lesson I had this function:

def wc(document: String): VectorMap[String, Int] = 
    val stringWithoutNewlines = 
        replaceNewlinesWithBlanks(document)
    val stringWithoutFormatting = 
        stripFormattingCharacters(stringWithoutNewlines)
    val stringWithSingleBlanks = 
        squeezeBlankSpaces(stringWithoutFormatting)
    val listOfWords = 
        convertStringToListOfWords(stringWithSingleBlanks)
    val lcListOfWords = 
        lowerCaseAllWords(listOfWords)
    val initialMap = 
        convertWordListToWordCount(lcListOfWords)
    val sortedMap = 
        sortMapByHighestValue(initialMap)
    sortedMap

But because initialMap (near the end of the function) is exactly equal to convertWordListToWordCount(lcListOfWords) — and always will be, because the values are immutable and the functions are pure — you can replace initialMap in the second-to-last line with its equivalent function call, like this:

def wc(document: String): VectorMap[String, Int] = 
    val stringWithoutNewlines = 
        replaceNewlinesWithBlanks(document)
    val stringWithoutFormatting = 
        stripFormattingCharacters(stringWithoutNewlines)
    val stringWithSingleBlanks = 
        squeezeBlankSpaces(stringWithoutFormatting)
    val listOfWords = 
        convertStringToListOfWords(stringWithSingleBlanks)
    val lcListOfWords = 
        lowerCaseAllWords(listOfWords)
    // ELIMINATED 'initialMap'
    val sortedMap = 
        sortMapByHighestValue(convertWordListToWordCount(lcListOfWords))
    sortedMap

By the same argument, lcListOfWords is exactly equal to:

lowerCaseAllWords(listOfWords)

so I can eliminate that intermediate variable:

def wc(document: String): VectorMap[String, Int] = 
    val stringWithoutNewlines = 
        replaceNewlinesWithBlanks(document)
    val stringWithoutFormatting = 
        stripFormattingCharacters(stringWithoutNewlines)
    val stringWithSingleBlanks = 
        squeezeBlankSpaces(stringWithoutFormatting)
    val listOfWords = 
        convertStringToListOfWords(stringWithSingleBlanks)
    // ELIMINATED 'lcListOfWords'
    val sortedMap = 
        sortMapByHighestValue(
            convertWordListToWordCount(
                lowerCaseAllWords(listOfWords)
            )
        )
    sortedMap

Next, listOfWords is exactly equal to:

convertStringToListOfWords(stringWithSingleBlanks)

and always will be — so I can remove listOfWords as an intermediate value:

def wc(document: String): VectorMap[String, Int] = 
    val stringWithoutNewlines = 
        replaceNewlinesWithBlanks(document)
    val stringWithoutFormatting = 
        stripFormattingCharacters(stringWithoutNewlines)
    val stringWithSingleBlanks = 
        squeezeBlankSpaces(stringWithoutFormatting)
    // ELIMINATED 'listOfWords'
    val sortedMap = 
        sortMapByHighestValue(
            convertWordListToWordCount(
                lowerCaseAllWords(
                    convertStringToListOfWords(stringWithSingleBlanks)
                )
            )
        )
    sortedMap

The same is true of stringWithSingleBlanks, so I reduce the code again:

def wc(document: String): VectorMap[String, Int] = 
    val stringWithoutNewlines = 
        replaceNewlinesWithBlanks(document)
    val stringWithoutFormatting = 
        stripFormattingCharacters(stringWithoutNewlines)
    // ELIMINATED 'stringWithSingleBlanks'
    val sortedMap = 
        sortMapByHighestValue(
            convertWordListToWordCount(
                lowerCaseAllWords(
                    convertStringToListOfWords(
                        squeezeBlankSpaces(stringWithoutFormatting)
                    )
                )
            )
        )
    sortedMap

and then do the same with stringWithoutFormatting:

def wc(document: String): VectorMap[String, Int] = 
    val stringWithoutNewlines = 
        replaceNewlinesWithBlanks(document)
    // ELIMINATED 'stringWithoutFormatting'
    val sortedMap = 
        sortMapByHighestValue(
            convertWordListToWordCount(
                lowerCaseAllWords(
                    convertStringToListOfWords(
                        squeezeBlankSpaces(
                            stripFormattingCharacters(stringWithoutNewlines)
                        )
                    )
                )
            )
        )
    sortedMap

and then stringWithoutNewlines:

def wc(document: String): VectorMap[String, Int] = 
    // ELIMINATED 'stringWithoutNewlines'
    val sortedMap = 
        sortMapByHighestValue(
            convertWordListToWordCount(
                lowerCaseAllWords(
                    convertStringToListOfWords(
                        squeezeBlankSpaces(
                            stripFormattingCharacters(
                                replaceNewlinesWithBlanks(document)
                            )
                        )
                    )
                )
            )
        )
    sortedMap

And if you want to, you can eliminate sortedMap:

def wc(document: String): VectorMap[String, Int] = 
    // ELIMINATED 'sortedMap'
    sortMapByHighestValue(
        convertWordListToWordCount(
            lowerCaseAllWords(
                convertStringToListOfWords(
                    squeezeBlankSpaces(
                        stripFormattingCharacters(
                            replaceNewlinesWithBlanks(document)
                        )
                    )
                )
            )
        )
    )

To be clear, you DO NOT have to write code like this. I’m just showing it to demonstrate a possibility of this style of programming.

Algebraic substitution

We call this process algebraic substitution, and it works because:

  • The functions are pure
  • The variables are immutable
  • The data structures are immutable

When code is written like this, both you and the compiler are perfectly free to write it in any of these ways, and you’re always guaranteed to get the same result.

KEY: But if you use mutable variables, mutable data types, and impure methods, the same cannot be said.

Technical goo: “Referential Transparency”

If you like algebra, you’ll like referential transparency. We say that an expression is referentially transparent (RT) if it can be replaced by its resulting value without changing the behavior of the program. This must be true regardless of where the expression is used in the program. So this is basically a way of saying, “Algebraic substitution can be done here.”

What I did in the previous example is actually the opposite of that — I replaced the intermediate variables with their expressions — but that’s the cool part: all of those intermediate variables and their pure function calls are 100% equivalent.

Finally, notice that I’m not doing any “fancy FP” stuff in this code. I’m just writing EOP code with immutable variables, immutable data types, and pure functions.

Update: All of my new videos are now on
LearnScala.dev