Functional Thinking

Chapter 1. Why

Let’s say for a moment that you are a lumberjack. You have the best axe in the forest, which makes you the most productive lumberjack in the camp. Then one day someone shows up and extols the virtues of a new tree-cutting paradigm, the chainsaw. The sales guy is persuasive, so you buy a chainsaw, but you don’t know how it works. Demonstrating your expertise with the previous tree-cutting paradigm, you swing it vigorously at a tree—without cranking it. You quickly conclude that this newfangled chainsaw is a fad, and you return to your axe. Then, someone appears and shows you how to crank the chainsaw.

The problem with a completely new programming paradigm isn’t learning a new language. After all, everyone reading this has learned numerous computer languages—language syntax is merely details. The tricky part is learning to think in a different way.

This book explores the subject of functional programming but isn’t really about functional programming languages. Make no mistake—I show lots of code, in numerous languages; this book is all about code. As I’ll illustrate, writing code in a “functional” manner touches on design trade–offs, different reusable building blocks, and a host of other insights. Because I favor ideas over syntax, I start with Java, the most familiar baseline for the largest group of developers, and mix in both pre-Java 8 and Java 8 examples. As much as possible, I show functional programming concepts in Java (or close relatives) and move to other languages only to demonstrate unique capabilities.

Even if you don’t care about Scala or Clojure, and are happy coding in your current language for the rest of your career, your language will change underneath you, looking more functional all the time. Now is the time to learn functional paradigms, so that you can leverage them when (not if) they appear in your everyday language. Let’s take a look at the reasons why all languages are gradually becoming more functional.

Shifting Paradigms

Computer science often advances in fits and starts, with good ideas appearing decades before they suddenly become part of the mainstream. For example, Simula 67, created in 1967, is the first object-oriented language, yet object orientation didn’t really become mainstream until after the popularization of C++, which first appeared in 1983. Often, good ideas await foundation technologies to catch up. In its early years, Java was regularly considered too slow and expansive in memory usage for high-performance applications, but shifts in the hardware market made it an attractive choice.

Functional programming follows the same conceptual trajectory as object orientation: developed in academia over the last few decades, it has slowly crept into all modern programming languages. Yet just adding new syntax to a language doesn’t inform developers of the best way to leverage this new way of thinking.

I start with a contrast between the traditional programming style (imperative loops) and a more functional way of solving the same problem. For the problem to solve, I dip into a famous event in computer science history, a challenge issued from Jon Bentley, the writer of a regular column in Communications of the ACM called “Programming Pearls,” to Donald Knuth, an early computer science pioneer. The challenge is common to anyone who has written text-manipulation code: read a file of text, determine the most frequently used words, and print out a sorted list of those words along with their frequencies. Just tackling the word-frequency portion, I write a solution in “traditional” Java, shown in Example 1-1.

Example 1-1. Word frequencies in Java

public class Words {
    private Set<String> NON_WORDS = new HashSet<String>() {{
        add("the"); add("and");	add("of"); add("to"); add("a");
        add("i"); add("it"); add("in");	add("or"); add("is");
        add("d"); add("s"); add("as"); add("so"); add("but");
        add("be");
	}};

    public Map wordFreq(String words) {
        TreeMap<String, Integer> wordMap = new TreeMap<String, Integer>();
        Matcher m = Pattern.compile("\\w+").matcher(words);
        while (m.find()) {
            String word = m.group().toLowerCase();
            if (! NON_WORDS.contains(word)) {
                if (wordMap.get(word) == null) {
                    wordMap.put(word, 1);
                }
                else {
                    wordMap.put(word, wordMap.get(word) + 1);
                }
            }
        }
        return wordMap;
    }
}

In Example 1-1, I create a set of nonwords (articles and other “glue” words), then create the wordFreq() method. In it, I build a Map to hold the key/value pairs, then create a regular expression to allow me to determine words. The bulk of this listing iterates over the found words, ensuring that the actual word is either added the first time to the map or its occurrence is incremented. This style of coding is quite common in languages that encourage you to work through collections (such as regular expression matches) piecemeal.

Consider the updated version that takes advantage of the Stream API and the support for higher-order functions via lambda blocks in Java 8 (all discussed in more detail later), shown in Example 1-2.

Example 1-2. Word frequency in Java 8

private List<String> regexToList(String words, String regex) {
    List wordList = new ArrayList<>();
    Matcher m = Pattern.compile(regex).matcher(words);
    while (m.find())
    wordList.add(m.group());
    return wordList;
}

public Map wordFreq(String words) {
    TreeMap<String, Integer> wordMap = new TreeMap<>();
    regexToList(words, "\\w+").stream()
            .map(w -> w.toLowerCase())
            .filter(w -> !NON_WORDS.contains(w))
            .forEach(w -> wordMap.put(w, wordMap.getOrDefault(w, 0) + 1));
    return wordMap;
}

In Example 1-2, I convert the results of the regular expression match to a stream, which allows me to perform discrete operations: make all the entries lowercase, filter out the nonwords, and count the frequencies of the remaining words. By converting the iterator returned via find() to a stream in the regexToList() method, I can perform the required operations one after the other, in the same way that I think about the problem. Although I could do that in the imperative version in Example 1-1 by looping over the collection three times (once to make each word lowercase, once to filter nonwords, and once to count occurrences), I know not to do that because it would be terribly inefficient. By performing all three operations within the iterator block in Example 1-1, I’m trading clarity for performance. Although this is a common trade-off, it’s one I’d rather not make.

In his “Simple Made Easy” keynote at the Strange Loop conference, Rich Hickey, the creator of Clojure, reintroduced an arcane word, complect: to join by weaving or twining together; to interweave. Imperative programming often forces you to complect your tasks so that you can fit them all within a single loop, for efficiency. Functional programming via higher-order functions such as map() and filter() allows you to elevate your level of abstraction, seeing problems with better clarity. I show many examples of functional thinking as a powerful antidote to incidental complecting.

Aligning with Language Trends

If you look at the changes coming to all major languages, they all add functional extensions. Groovy has been adding functional capabilities for a while, including advanced features such as memoization (the ability for the runtime to cache function return values automatically). Even Java itself will finally grow more functional extensions, as lambda blocks (i.e., higher-order functions) finally appear in Java 8, and arguably the most widely used language, JavaScript, has numerous functional features. Even the venerable C++ added lambda blocks in the language’s 2011 standard, and has generally shown more functional programming interest, including intriguing libraries such as the Boost.Phoenix library.

Learning these paradigms now allows you to utilize the features as soon as they appear, either in your use of a new language such as Clojure or in the language you use every day. In Chapter 2, I cover how to shift your thinking to take advantage of these advanced facilities.

Ceding Control to the Language/Runtime

During the short history of computer science, the mainstream of technology sometimes spawns branches, either practical or academic. For example, in the 1990s, the move to personal computers saw an explosion in popularity of fourth-generation languages (4GL) such as dBASE, Clipper, FoxPro, Paradox, and a host of others. One of the selling points of these languages was a higher-level abstraction than a 3GL like C or Pascal. In other words, you could issue a single command in a 4GL that would take many commands in a 3GL because the 4GL already had more “prebaked” context. These languages were already equipped to read popular database formats from disk rather than force customized implementations.

Functional programming is a similar offshoot from academia, where computer scientists wanted to find ways of expressing new ideas and paradigms. Every so often, a branch will rejoin the mainstream, which is what is happening to functional programming now. Functional languages are sprouting not just on the Java Virtual Machine (JVM), where the two most interesting new languages are Scala and Clojure, but on the .NET platform as well, which includes F# as a first-class citizen. Why this embrace of functional programming by all the platforms?

Back in the early 1980s, when I was in university, we used a development environment called Pecan Pascal, whose unique feature was the ability to run the same Pascal code on either the Apple ][ or IBM PC. The Pecan engineers achieved this feat by using something mysterious called “bytecode.” When the developer compiled his code, he compiled it to this “bytecode,” which ran on a “virtual machine,” written natively for each of the two platforms. And it was a hideous experience. The resulting code was achingly slow even for simple class assignments. The hardware at the time just wasn’t up to the challenge.

Of course, we all recognize this architecture. A decade after Pecan Pascal, Sun released Java using the same techniques, straining but succeeding in mid-1990s hardware environments. It also added other developer-friendly features, such as automatic garbage collection. I never want to code in a non-garbage-collected language again. Been there, done that, got the T-shirt, and don’t want to go back, because I’d rather spend my time at a higher level of abstraction, thinking about ways to solve complex business scenarios, not complicated plumbing problems. I rejoice in the fact that Java reduces the pain of explicit memory management, and I try to find that same level of convenience in other places.

Note

Life’s too short for malloc.

Over time, developers cede more control over tedious tasks to our languages and runtimes. I don’t lament the lack of direct memory control for the types of applications I write, and ignoring that allows me to focus on more important problems. Java eased our interaction with memory management; functional programming languages allow us to replace other core building blocks with higher-order abstractions.

Examples of replacing detailed implementations with simpler ones relying on the runtime to handle mundane details abound in this book.

Concision

Michael Feathers, author of Working with Legacy Code, captured a key difference between functional and object-oriented abstractions in 140 lowly characters on Twitter:

OO makes code understandable by encapsulating moving parts. FP makes code understandable by minimizing moving parts.

— Michael Feathers

Think about the things you know about object-oriented programming (OOP) constructs: encapsulation, scoping, visibility, and other mechanisms exist to exert fine-grained control over who can see and change state. More complications pile up when you deal with state plus threading. These mechanisms are what Feathers referred to as “moving parts.” Rather than build mechanisms to control mutable state, most functional languages try to remove mutable state, a “moving part.” The theory follows that if the language exposes fewer potentially error-prone features, it is less likely for developers to make errors. I will show numerous examples throughout of functional programming eliminating variables, abstractions, and other moving parts.

In object-oriented imperative programming languages, the units of reuse are classes and the messages they communicate with, captured in a class diagram. The seminal work in that space, Design Patterns: Elements of Reusable Object-Oriented Software (by Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides), includes at least one class diagram with each pattern. In the OOP world, developers are encouraged to create unique data structures, with specific operations attached in the form of methods. Functional programming languages don’t try to achieve reuse in quite the same way. In functional programming languages, the preference is for a few key data structures (such as list, set, and map) with highly optimized operations on those data structures. To utilize this machinery, developers pass data structures plus higher-order functions to plug into the machinery, customizing it for a particular use.

Consider a simplified portion of the code from Example 1-2:

regexToList(words, "\\b\\w+\\b").stream()
                .filter(w -> !NON_WORDS.contains(w))

To retrieve a subset of a list, call the filter() method, passing the list as a stream of values and a higher-order function specifying the filter criteria (in this case, the syntactically sugared (w → !NON_WORDS.contains(w))). The machinery applies the filter criteria in an efficient way, returning the filtered list.

Encapsulation at the function level allows reuse at a more granular, fundamental level than building new class structures for every problem. Dozens of XML libraries exist in the Java world, each with its own internal data structures. One advantage of leveraging higher-level abstractions is already appearing in the Clojure space. Recent clever innovations in Clojure’s libraries have managed to rewrite the map function to be automatically parallelizable, meaning that all map operations get a performance boost without developer intervention.

Functional programmers prefer a few core data structures, building optimized machinery to understand them. Object-oriented programmers tend to create new data structures and attendant operations constantly—building new classes and messages between them is the predominant object oriented paradigm. Encapsulating all data structures within classes discourages reuse at the method level, preferring larger framework-style reuse. Functional programming constructs make it easier to reuse code at a more atomic level.

Consider the indexOfAny() method, from the popular Java framework Apache Commons, which provides a slew of helpers for Java, in Example 1-3.

Example 1-3. indexOfAny() from Apache Commons StringUtils

// From Apache Commons Lang, http://commons.apache.org/lang/
public static int indexOfAny(String str, char[] searchChars) {
    if (isEmpty(str) || ArrayUtils.isEmpty(searchChars)) { 
        return INDEX_NOT_FOUND;
    }
    int csLen = str.length();                    
    int csLast = csLen - 1;
    int searchLen = searchChars.length;
    int searchLast = searchLen - 1;
    for (int i = 0; i < csLen; i++) {            
        char ch = str.charAt(i);
        for (int j = 0; j < searchLen; j++) {    
            if (searchChars[j] == ch) {          
                if (i < csLast && j < searchLast && CharUtils.isHighSurrogate(ch)) {
                    if (searchChars[j + 1] == str.charAt(i + 1)) {
                        return i;
                     }
                 } else {
                     return i;
                 }
             }
         }
     }
     return INDEX_NOT_FOUND;
}

Safety checks

Initialization

Outer iteration

Inner iteration

Decisions, decisions, decisions

The IndexofAny() method accepts a String and an array and returns the index of the first occurrence in the String of any of the characters in the array (thus the name index of any). The documentation includes examples of what is returned for given inputs, as shown in Example 1-4.

Example 1-4. indexOfAny() example cases

StringUtils.indexOfAny("zzabyycdxx",['z','a']) == 0
StringUtils.indexOfAny("zzabyycdxx",['b','y']) == 3
StringUtils.indexOfAny("aba", ['z'])           == -1

As you can see in Example 1-4, the first occurrence of z or a within zzabyycdxx is at index 0, and the first occurrence of b or y is at position 3.

The essence of this problem can be stated as: for each of the searchChars, find the index of the first encountered match within the target string. The Scala implementation of this method, called firstIndexOfAny, is much more straightforward, as shown in Example 1-5.

Example 1-5. Scala version of firstIndexOfAny()

def firstIndexOfAny(input : String, searchChars : Seq[Char]) : Option[Int] = {
  def indexedInput = (0 until input.length).zip(input)
  val result = for (pair <- indexedInput;
                    char <- searchChars;
                    if (char == pair._2)) yield (pair._1)
  if (result.isEmpty)
    None
  else
    Some(result.head)
}

In Example 1-5, I create an indexed version of the input string. Scala’s zip() method takes a collection (the range of numbers up to the length of my input string) and combines it with the collection of String characters, creating a new collection consisting of pairs from the original collection. For example, if my input string is zabycdxx, indexedInput contains Vector ((0,z), (1,a), (2,b), (3,y), (4,c), (5,d), (6,x), (7,x)). The zip name comes from the result; it looks as if the two collections have been joined like the teeth of a zipper.

Once I have the indexed collection, I use Scala’s for() comprehension to first look at the collection of search characters, then access each pair from the indexed collection. Scala allows shorthand access to collection elements, so I can compare the current search character to the second item for the collection (if (char == pair._2))). If the characters match, I return the index portion of the pair (pair._1).

A common source of confusion in Java is the presence of null: is it a legitimate return value or does it represent the absence of a value? In many functional langugages (Scala included), that ambiguity is avoided by the Option class, which contains either None, indicating no return, or Some, containing the returned values. For Example 1-5, the problems asks for only the first match, so I return result.head, the first element in the results collection.

The original mandate of the problem asked for the first match, but it is trivial to create a version that returns all matches. I can rewrite my example to return all the matches by changing the return type and eliminating the wrapper around the return value, as shown in Example 1-6.

Example 1-6. Returning a lazy list of matches

def indexOfAny(input : String, searchChars : Seq[Char]) : Seq[Int] = {
  def indexedInput = (0 until input.length).zip(input)
  for (pair <- indexedInput;
       char <- searchChars;
       if (char == pair._2)) yield (pair._1)
}

Rather than constrain the API, allow the consumer to decide how many values it needs. Running firstIndexOfAny("zzabyycdxx", "by") returns 3 whereas indexOfAny("zzabyycdxx", "by") returns Vector(3, 4, 5).