Chapter 4. Smarter, Not Harder

Switching paradigms yields benefits, allowing you to get more work done with less effort. Many functional programming constructs do just that: remove annoying implementation details for common problems.

In this chapter, I discuss two features common in functional languages: memoization and laziness.

Memoization

The word memoization was coined by Donald Michie, a British artificial-intelligence researcher, to refer to function-level caching for repeating values. Today, memoization is common in functional programming languages, either as a built-in feature or one that’s relatively easy to implement.

Memoization helps in the following scenario. Suppose you have a performance-intensive function that you must call repeatedly. A common solution is to build an internal cache. Each time you calculate the value for a certain set of parameters, you put that value in the cache, keyed to the parameter value(s). In the future, if the function is invoked with previous parameters, return the value from the cache rather than recalculate it. Function caching is a classic computer science trade-off: it uses more memory (which we frequently have in abundance) to achieve better performance over time.

Functions must be pure for the caching technique to work. A pure function is one that has no side effects: it references no other mutable class fields, doesn’t set any values other than the return value, and relies only on the parameters for input. All the methods in the java.lang.Math class are excellent examples of pure functions. Obviously, you can reuse cached results successfully only if the function reliably returns the same values for a given set of parameters.

Caching

Caching is a common requirement (and source of hard-to-find bugs). In this section, I investigate two caching use cases for functions: intraclass versus external calls. I also illustrate two alternatives for implementing caching: hand-crafted state and memoization.

Method-level caching

In previous chapters, I’ve used the number classification problem as a canvas for solutions. The Classifier class classifies numbers, and a common use for it would entail running the same number through multiple methods for classification. For example, consider this code:

if (Classifier.isPerfect(n)) print "!"
else if (Classifier.isAbundant(n)) print "+"
else if (Classifier.isDeficient(n)) print "-"

In the previous implementations, I must recalculate the sum of the factors for every classification method that I call. This is an example of intraclass caching: during normal use, the sumOfFactors() method is typically called multiple times per number. In this common use case, this is an inefficient approach.

Caching sum

One of the ways to make the code more efficient is to leverage hard work already done. Because generating the sum of the factors is expensive, I want to do it only once for each number. Toward that end, I create a cache to store calculations, as shown in Example 4-1.

Example 4-1. Caching sum
class ClassifierCachedSum {
  private sumCache = [:]

  def sumOfFactors(number) {
    if (! sumCache.containsKey(number)) {
      sumCache[number] = factorsOf(number).sum()
    }
   return sumCache[number]

  }
// remainder of code unchanged...

In Example 4-1, I create a hash named sumCache as part of the class initialization. In the sumOfFactors() method, I check to see if the sum for the parameter is already cached and return it. Otherwise, I do the expensive calculation and put the sum in the cache before returning it.

The code is more complicated, but the results speak for themselves. I run all the examples through a series of unit tests that follow the pattern shown in Example 4-2.

Example 4-2. Testing nonoptimized speed
  def static final TEST_NUMBER_MAX = 5000

  @Test
  void mashup() {
    println "Test for range 1-${TEST_NUMBER_MAX}"
    print "Non-optimized:              "
    start = System.currentTimeMillis()
    (1..TEST_NUMBER_MAX).each {n ->
      if (Classifier.isPerfect(n)) print '!'
      else if (Classifier.isAbundant(n)) print '+'
      else if (Classifier.isDeficient(n)) print '-'
    }
    println "\n\t ${System.currentTimeMillis() - start} ms"
    print "Non-optimized (2nd):        "
    start = System.currentTimeMillis()
    (1..TEST_NUMBER_MAX).each {n ->
      if (Classifier.isPerfect(n)) print '!'
      else if (Classifier.isAbundant(n)) print '+'
      else if (Classifier.isDeficient(n)) print '-'
    }
    println "\n\t ${System.currentTimeMillis() - start} ms"

When I run the tests in Example 4-2, the results in Table 4-1 indicate that the caching helps.

Table 4-1. Results for range 1–1,000
Version Results (smaller is better)

Nonoptimized

577 ms

Nonoptimized (2nd)

280 ms

Cached sum

600 ms

Cached sum (2nd)

50 ms

The output illustrates that the nonoptimized version runs in 577 ms the first time, compared to the cached version, which takes 600 ms for its first run. For these two cases, the difference is insignificant, and you can see the slight overhead to build the cache. However, the second run of the nonoptimized version scores 280 ms. The difference between the first and second can be attributed to environmental factors such as garbage collection. The second run of the cached version shows a dramatic speed increase, scoring a mere 50 ms. When the second run happens, all the values are cached; now I’m measuring how fast I can read from a hash. The difference between the nonoptimized first run and the cached first run is negligible, but it’s dramatic for the second run. This is an example of external caching: the overall results are used by whoever is calling the code, so the second run is very fast.

Caching sums makes a huge difference but includes trade-offs. ClassifierCachedSum can no longer contain pure static methods. The internal cache represents state, so I must make all the methods that interact with the cache nonstatic, which has a ripple effect. I could rig some Singleton solution, but that adds complexity too and a raft of testing issues. Because I control the cache variable, I must ensure correctness (by using tests, for example). Although caching improves performance, it isn’t free: it adds accidental complexity and a maintenance burden to my code.

Caching everything

If caching the sums speeds up the code so much, why not cache every intermediate result that’s likely to recur? That’s the goal in Example 4-3.

Example 4-3. Caching everything
class ClassifierCached {
  private sumCache = [:], factorCache = [:]

  def sumOfFactors(number) {
    if (! sumCache.containsKey(number))
      sumCache[number] = factorsOf(number).sum()
    sumCache[number]
  }

  def isFactor(number, potential) {
    number % potential == 0;
  }

  def factorsOf(number) {
    if (! factorCache.containsKey(number))
      factorCache[number] = (1..number).findAll {isFactor(number, it)}
    factorCache[number]
  }

  def isPerfect(number) {
    sumOfFactors(number) == 2 * number
  }

  def isAbundant(number) {
    sumOfFactors(number) > 2 * number
  }

  def isDeficient(number) {
    sumOfFactors(number) < 2 * number
  }

}

In ClassifierCached in Example 4-3, I add caches both for the sum of factors and for the factors of a number—the increased performance appears in the test run results in Table 4-2.

Table 4-2. Results for range 1–1,000
Version Results (smaller is better)

Nonoptimized

577 ms

Nonoptimized (2nd)

280 ms

Cached sum

600 ms

Cached sum (2nd)

50 ms

Cached

411 ms

Cached (2nd)

38 ms

The fully cached version (which is an entirely new class and instance variable in these test runs) scores 411 ms for the first run and a blazing 38 ms in the second run, once the cache has been primed. Although these results are good, this approach doesn’t scale particularly well. In this test run, which shows results for testing 8,000 numbers, the outcome is more dire:

java.lang.OutOfMemoryError: Java heap space
        at java.util.ArrayList.<init>(ArrayList.java:112)
...more bad things...

As these results show, the developer responsible for the caching code must worry about both its correctness and its execution conditions. This is a perfect example of moving parts: state in code that a developer must maintain and dissect implications for. Many languages have advanced beyond this constraint, using mechanisms like memoization.

Adding Memoization

Functional programming strives to minimize moving parts by building reusable mechanisms into the runtime. Memoization is a feature built into a programming language that enables automatic caching of recurring function-return values. In other words, it automatically supplies the code I’ve written in Examples 4-1 and 4-3. Many modern languages support memoization, including Groovy.

In order to memoize a function in Groovy, you define it as a closure, then execute the memoize() method to return a function whose results will be cached.

Memoizing a function is a metafunction application: doing something to the function itself rather than the function results. Currying, discussed in Chapter 3, is another example of a metafunction technique. Groovy built memoization into its Closure class; other languages implement it differently.

To implement caching for sumOfFactors() as I did in Example 4-1, I memoize the sumOfFactors() method, as shown in Example 4-4.

Example 4-4. Memoizing sum
package com.nealford.ft.memoization

class ClassifierMemoizedSum {
  def static isFactor(number, potential) {
    number % potential == 0;
  }

  def static factorsOf(number) {
    (1..number).findAll { i -> isFactor(number, i) }
  }

  def static sumFactors = { number ->
    factorsOf(number).inject(0, {i, j -> i + j})
  }
  def static sumOfFactors = sumFactors.memoize()

  def static isPerfect(number) {
    sumOfFactors(number) == 2 * number
  }

  def static isAbundant(number) {
    sumOfFactors(number) > 2 * number
  }

  def static isDeficient(number) {
    sumOfFactors(number) < 2 * number
  }
}

In Example 4-4, I create the sumFactors() method as a code block (note the = and parameter placement). This is a pretty generic method and could just as well be pulled from a library somewhere. To memoize it, I assign the name sumOfFactors as the memoize() method call on the function reference.

Running the memoized version yields the results shown in Table 4-3.

Table 4-3. Results for range 1–1,000
Version Results (smaller is better)

Nonoptimized

577 ms

Nonoptimized (2nd)

280 ms

Cached sum

600 ms

Cached sum (2nd)

50 ms

Cached

411 ms

Cached (2nd)

38 ms

Partially memoized

228 ms

Partially memoized (2nd)

60 ms

The partially memoized second run shows the same dramatic speed increase as the handwritten cached-sum version—with literally a two-line change to the original code (changing sumFactors() into a code block, and making sumOfFactors() point to a memoized instance of the code block).

Just as I cached everything earlier, why not memoize everything with potentially reusable results? That version of the classifier appears in Example 4-5, with the results shown in Table 4-4.

Example 4-5. Memoizing everything
package com.nealford.ft.memoization

class ClassifierMemoized {
  def static dividesBy = { number, potential ->
    number % potential == 0
  }
  def static isFactor = dividesBy.memoize()

  def static factorsOf(number) {
    (1..number).findAll { i -> isFactor.call(number, i) }
  }

  def static sumFactors = { number ->
    factorsOf(number).inject(0, {i, j -> i + j})
  }
  def static sumOfFactors = sumFactors.memoize()

  def static isPerfect(number) {
    sumOfFactors(number) == 2 * number
  }

  def static isAbundant(number) {
    sumOfFactors(number) > 2 * number
  }

  def static isDeficient(number) {
    sumOfFactors(number) < 2 * number
  }
}
Table 4-4. Results for range 1–1,000
Version Results (smaller is better)

Nonoptimized

577 ms

Nonoptimized (2nd)

280 ms

Cached sum

600 ms

Cached sum (2nd)

50 ms

Cached

411 ms

Cached (2nd)

38 ms

Partially memoized

228 ms

Partially memoized (2nd)

60 ms

Memoized

956 ms

Memoized (2nd)

19 ms

Memoizing everything slows down the first run but has the fastest subsequent run of any case—but only for small sets of numbers. As with the imperative caching solution tested in Example 4-3, large number sets impede performance drastically. In fact, the memoized version runs out of memory in the 8,000-number case. But for the imperative approach to be robust, safeguards and careful awareness of the execution context are required—another example of imperative moving parts. With memoization, optimization occurs at the function level. Look at the memoization results for 10,000 numbers found in Table 4-5.

Table 4-5. Results for range 1–10,000
Version Results (smaller is better)

Nonoptimized

41,909 ms

Nonoptimized (2nd)

22,398 ms

Memoize at most 1000

55,685 ms

Memoize at most 1000 (2nd)

98 ms

I produced the results in Table 4-5 by calling the memoizeAtMost(1000) method instead of memoize(). Like other languages that support memoization, Groovy has several methods to help optimize results, as shown in Table 4-6.

Table 4-6. Memoization methods in Groovy
Method Description

memoize()

Creates a caching variant of the closure

memoizeAtMost()

Creates a caching variant of the closure with an upper limit on the cache size

memoizeAtLeast()

Creates a caching variant of the closure with automatic cache size adjustment and lower limit on the cache size

memoizeBetween()

Creates a caching variant of the closure with automatic cache size adjustment and lower and upper limits on the cache size

In the imperative version, the developer owns the code (and responsibility). Functional languages build generic machinery—sometimes with customization knobs (in the form of alternate functions or parameters)—that you can apply to standard constructs. Functions are a fundamental language element, so optimizing at that level gives you advanced functionality for free. The memoization versions in this chapter with small number sets outperform the handwritten caching code handily. In fact, I’ll never be able to create a cache as efficient as the language designers can because they can bend their own rules: language designers have access to low-level parts that developers don’t, providing optimization opportunities beyond the grasp of mere mortals. Not only can the language handle caching more efficiently, I want to cede that responsibility to the runtime so I can think about problems at a higher level of abstraction.

Note

Language designers will always build more efficient mechanisms because they are allowed to bend rules.

Building a cache by hand is straightforward, but it adds statefulness and complexity to the code. Using functional-language features like memoization, I can add caching at the function level, achieving better results (with virtually no change to my code) than the imperative version. Functional programming eliminates moving parts, allowing you to focus your energy on solving real problems.

Of course, you don’t have to rely on an existing class to layer memoization atop it. The memoize() family of functions is implemented as part of the Closure library class. Consider the example of inline memoization declaration shown in Example 4-6.

Example 4-6. Inline memoization in Groovy
package com.nealford.javanext.memoizehashing

class NameHash {
  def static hash = {name ->
    name.collect{rot13(it)}.join()
  }.memoize()

  public static char rot13(s) {
    char c = s
    switch (c) {
      case 'A'..'M':
      case 'a'..'m': return c + 13
      case 'N'..'Z':
      case 'n'..'z': return c - 13
      default: return c
    }
  }

}

I don’t mean to suggest that the rot13() algorithm (a version of the Caesar Cipher) in Example 4-6 is performance challenged, so just pretend that it is worth caching. Note the slightly unusual function-definition syntax in the assignment of the code block to the hash variable. The last part of the definition is the call to memoize(), meaning that a nonmemoized version doesn’t exist in this case.

A unit test that calls the memoized function appears in Example 4-7.

Example 4-7. Testing memoized hashing function
class NameHashTest extends GroovyTestCase {
  void testHash() {
    assertEquals("ubzre", NameHash.hash.call("homer"))  }
}

In Example 4-7, I must call the memoized function with an extra call() invocation. Generally, in Groovy, you can execute the contents of a code block with the syntactic sugar of just the variable name followed by parenthesis (NameHash.hash("Homer")) , which is executing the call() method by default. In this case, however, you must execute the memoized function via an explicit invocation to call().

Most functional languages either include memoization or make it trivial to implement. For example, memoization is built into Clojure; you can memoize any function by using the built-in (memoize ) function. For example, if you have an existing (hash ) function, you can memoize it via (memoize (hash "homer")) for a caching version. Example 4-8 implements the name-hashing algorithm from Example 4-6 in Clojure.

Example 4-8. Memoization in Clojure
(ns name-hash.core)
(use '[clojure.string :only (join split)])


(let [alpha (into #{} (concat (map char (range (int \a) (inc (int \z))))
                              (map char (range (int \A) (inc (int \Z))))))
      rot13-map (zipmap alpha (take 52 (drop 26 (cycle alpha))))]

  (defn rot13
    "Given an input string, produce the rot 13 version of
     the string. \"hello\" -> \"uryyb\""
    [s]
    (apply str (map #(get rot13-map % %) s))))

(defn name-hash [name]
  (apply str (map #(rot13 %) (split name #"\d"))))

(def name-hash-m (memoize name-hash))

Note that in Example 4-7, calling the memoized function requires an invocation of the call() method. In the Clojure version, the memoized method call is exactly the same on the surface, with the added indirection and caching invisible to the method’s user.

Scala doesn’t implement memoization directly but has a collection method named getOrElseUpdate() that handles most of the work of implementing it, as shown in Example 4-9.

Example 4-9. Memoization implementation in Scala
def memoize[A, B](f: A => B) = new (A => B) {
    val cache = scala.collection.mutable.Map[A, B]()
    def apply(x: A): B = cache.getOrElseUpdate(x, f(x))
  }

def nameHash = memoize(hash)

The getOrElseUpdate() function in Example 4-9 is the perfect operator for building a cache: it either retrieves the matching value or creates a new entry when none exists.

It is worth reiterating the importance of immutability for anything you memoize. If your memoized function relies on anything other than parameters to generate its results, you will receive unpredictable outcomes. If your memoized function has side effects, you won’t be able to rely on that code executing when the cached value is returned.

Note

Make sure all memoized functions:

  • Have no side effects
  • Never rely on outside information

As runtimes become more sophisticated and we have plenty of machine resources at our disposal, advanced features such as memoization become common in just about every mainstream language. For example, although Java 8 doesn’t include native memoization, it is easy to implement it atop the new lambda features.

Note

Even if you don’t care about functional languages such as Scala or Clojure, functional programming will enter your life through the langauge(s) you now use as they evolve.

Laziness

Lazy evaluation—deferral of expression evaluation for as long as possible—is a feature of many functional programming languages. Lazy collections deliver their elements as needed rather than precalculating them, offering several benefits. First, you can defer expensive calculations until they’re absolutely needed. Second, you can create infinite collections, which keep delivering elements as long as they keep receiving requests. Third, lazy use of functional concepts such as map and filter enable you to generate more efficient code. Java doesn’t natively support laziness until Java 8, but several frameworks and successor languages do.

Consider the snippet of pseudocode for printing the length of a list in Example 4-10.

Example 4-10. Pseudocode illustrating nonstrict evaluation
print length([2+1, 3*2, 1/0, 5-4])

If you try to execute this code, the result will vary depending on the type of programming language it’s written in: strict or nonstrict (also known as lazy). In a strict programming language, executing (or perhaps even compiling) this code results in a DivByZero exception because of the list’s third element. In a nonstrict language, the result is 4, which accurately reports the number of items in the list. After all, the method I’m calling is length(), not lengthAndThrowExceptionWhenDivByZero()! Haskell is one of the few nonstrict languages in common use. Alas, Java doesn’t support nonstrict evaluation, but you can still take advantage of the concept of laziness in Java by deferring evaluation, and some next-generation languages are lazier than Java by default.

Lazy Iterator in Java

To build laziness, I require a data structure that supports the concept. Toward that end, consider the implementation of a prime number (a number divisible only by 1 and itself) in Example 4-11.

Example 4-11. Prime number finder in Java
package com.nealford.functionalthinking.primes;

import java.util.HashSet;
import java.util.Set;

import static java.lang.Math.sqrt;

public class Prime {

    public static boolean isFactor(final int potential, final int number) {
        return number % potential == 0;
    }

    public static Set<Integer> getFactors(final int number) {
        Set<Integer> factors = new HashSet<>();
        factors.add(1);
        factors.add(number);
        for (int i = 2; i < sqrt(number) + 1; i++)
            if (isFactor(i, number)) {
                factors.add(i);
                factors.add(number / i);
            }
        return factors;
    }

    public static int sumFactors(final int number) {
        int sum = 0;
        for (int i : getFactors(number))
            sum += i;
        return sum;
    }

    public static boolean isPrime(final int number) {
        return sumFactors(number) == number + 1;
    }

    public static Integer nextPrimeFrom(final int lastPrime) {
        int candidate = lastPrime + 1;
        while (!isPrime(candidate)) candidate++;
        return candidate;
    }

}

Java’s lack of native support for lazy collections doesn’t mean you can’t simulate one using an Iterator. For this example, using the helper in Example 4-11, I build an iterator that returns the next prime number on demand, shown in Example 4-12.

Example 4-12. Prime iterator in Java
package com.nealford.ft.laziness;

import java.util.Iterator;

public class PrimeIterator implements Iterator<Integer> {
    private int lastPrime = 1;

    @Override
    public boolean hasNext() {
        return true;
    }

    @Override
    public Integer next() {
        return lastPrime = Prime.nextPrimeFrom(lastPrime);
    }

    @Override
    public void remove() {
        throw new RuntimeException("Fundamental nature of the universe exception!");
    }
}

Generally, developers think of iterators as using collections as backing stores, but anything that supports the Iterator interface qualifies. In Example 4-12, the hasNext() method always returns true because, as far as we know, the number of prime numbers is infinite. The remove() method doesn’t apply here, so I throw an exception in case of accidental invocation. The workhorse method is the next() method, which handles two chores with its single line. First, it generates the next prime number based on the last one by calling the nextPrimeFrom() method that I added in Example 4-11. Second, it exploits Java’s ability to assign and return in a single statement, updating the internal lastPrime field.

Totally Lazy Number Classifier

You might think that the ability to write concise, functional code isn’t possible in Java until your company finally upgrades to Java 8. Although it’s impossible to retrofit higher-order functions on older versions of Java, several frameworks have used generics, anonymous classes, and static imports cleverly to yield some of the benefits elucidated earlier.

Back in Chapter 2, I introduced the number classification problem. Totally Lazy is a Java framework that bends Java syntax toward functional mechanisms, albeit in a wordy way. Consider the number classifier shown in Example 4-13.

Example 4-13. Number classifier using the Totally Lazy Java framework
import com.googlecode.totallylazy.Predicate;
import com.googlecode.totallylazy.Sequence;

import static com.googlecode.totallylazy.Predicates.is;
import static com.googlecode.totallylazy.numbers.Numbers.*;
import static com.googlecode.totallylazy.predicates.WherePredicate.where;

public class NumberClassifier {
    public static Predicate<Number> isFactor(Number n) {
         return where(remainder(n), is(zero));             1
     }

     public static Sequence<Number> getFactors(final Number n) {
         return range(1, n).filter(isFactor(n));
     }

     public static Sequence<Number> factors(final Number n) {
         return getFactors(n).memorise();
     }

     public static Number aliquotSum(Number n) {
         return subtract(factors(n).reduce(sum), n);
     }

     public static boolean isPerfect(Number n) {
         return equalTo(n, aliquotSum(n));
     }

     public static boolean isAbundant(Number n) {
         return greaterThan(aliquotSum(n), n);
     }

     public static boolean isDeficient(Number n) {
         return lessThan(aliquotSum(n), n);
     }}
1

Framework supplies functions like remainder and predicates like where.

A number of static imports allow me to eliminate some prefix noise. After the static imports are completed, the code is atypical of Java yet quite readable. Totally Lazy must augment Java within the syntactic bounds of Java, which eliminates operator overloading, by adding appropriate methods. Therefore, num % i == 0 becomes where(remainder(n), is(zero))

Some of the convenient syntax found in Totally Lazy was inspired by the Hamcrest testing extension for the JUnit testing framework and uses some of Hamcrest’s classes. The isFactor() method becomes a call to the where() method, using Totally Lazy’s remainder() method in conjunction with the Hamcrest is() method. Similarly, the factors() method becomes a filter() call on a range() object, and I use the now-familiar reduce() method to determine the sum. Java doesn’t support operator overloading, so even subtraction becomes a method call, as shown in aliquotSum’s subtract() call. Finally, the isPerfect() method uses Hamcrest’s equalTo() method to determine if the aliquot sum of factors equals the number.

Totally Lazy does an excellent job of using the lowly static import in Java to facilitate quite readable code. Many developers believe that Java is a poor host for internal domain-specific languages, but Totally Lazy debunks that attitude. And it uses laziness aggressively, deferring every possible operation.

To build more traditional lazy data structures, it’s useful to have higher-order functions.

Lazy Lists in Groovy

One of the common features of functional languages is the lazy list: a list whose contents are generated only as you need it. Lazy lists allow you to defer initialization of expensive resources until you absolutely need them. They also allow the creation of infinite sequences: lists that have no upper bound. If you aren’t required to say up front how big the list could be, you can let it be as big as it needs to be.

First, I illustrate using a lazy list in Groovy in Example 4-14, and then I’ll show you the implementation.

Example 4-14. Using lazy lists in Groovy
def prepend(val, closure) { new LazyList(val, closure) }

def integers(n) { prepend(n, { integers(n + 1) }) }

@Test
public void lazy_list_acts_like_a_list() {
    def naturalNumbers = integers(1)
    assertEquals('1 2 3 4 5 6 7 8 9 10', naturalNumbers.getHead(10).join(' '))
    def evenNumbers = naturalNumbers.filter { it % 2 == 0 }
    assertEquals('2 4 6 8 10 12 14 16 18 20', evenNumbers.getHead(10).join(' '))
}

The first method in Example 4-14, prepend(), creates a new LazyList, allowing you to prepend values. Readers familiar with functional languages might know this method as cons(), used to construct lists. The next method, integers(), returns a list of integers by using the prepend() method. The two parameters I send to the prepend() method are the initial value of the list and a code block that includes code to generate the next value. The integers() method acts like a factory that returns the lazy list of integers with a value at the front and a way to calculate additional values in the rear.

To retrieve values from the list, I call the getHead() method, which returns the argument number of values from the top of the list. In Example 4-14, naturalNumbers is a lazy sequence of all integers. To get a subset of them, I call the getHead() method, specifying how many integers I want. As the assertion indicates, I receive a list of the first 10 natural numbers. Using the filter() method, I retrieve a lazy list of even numbers and call the getHead() method to fetch the first 10 even numbers.

The implementation of LazyList appears in Example 4-15.

Example 4-15. LazyList implementation
package com.nealford.ft.allaboutlists

class LazyList {
    private head, tail

    LazyList(head, tail) {
        this.head = head;
        this.tail = tail
    }

    def LazyList getTail() { tail ? tail() : null }

    def List getHead(n) {
        def harvestedValues = [];
        def current = this
        n.times {
            harvestedValues << current.head
            current = current.tail
        }
        harvestedValues
    }

    def LazyList filter(Closure p) {
        if (p(head))
            p.owner.prepend(head, { getTail().filter(p) })
        else
            getTail().filter(p)
    }
}

A lazy list holds a head and tail, specified in the constructor. The getTail() method ensures that tail isn’t null and executes it. The getHead() method gathers the elements that I want to return, one at a time, pulling the existing element off the head of the list and asking the tail to generate a new value. The call to n.times {…} performs this operation for the number of elements requested, and the method returns the harvested values.

Lazy lists work great in situations in which generating resources are expensive, such as generating a list of perfect numbers.

Lazy list of perfect numbers

I discuss my favorite guinea-pig examples, perfect numbers, in Chapter 2. One of the shortcomings of all the implementations so far is the need to specify the number for classification. Instead, I want a version that returns a lazy list of perfect numbers. Toward that goal, I’ve written a highly functional, very compact perfect-number finder that supports lazy lists, shown in Example 4-16.

Example 4-16. Pared-down version of perfect-number classifier in Groovy
package com.nealford.ft.allaboutlists

import static com.nealford.ft.allaboutlists.NumberClassification.*

def enum NumberClassification {
  PERFECT, ABUNDANT, DEFICIENT
}

class NumberClassifier {
  static def factorsOf(number) {
    (1..number).findAll { i -> number % i == 0 }
  }

  static def classify(number) {
    switch (factorsOf(number).inject(0, { i, j -> i + j })) {
      case { it < 2 * number }: return DEFICIENT
      case { it > 2 * number }: return ABUNDANT
      case { it == 2 * number }: return PERFECT
    }
  }

  static def isPerfect(number) {
    classify(number) == PERFECT
  }


  static def nextPerfectNumberAfter(n) {
    while (!isPerfect(++n));
    n
  }
}

In Example 4-16, I create a compact classify() method, using the NumberClassification enumeration as the return value and checking each of the number classification rules against the implicit value it. I make use of the one new method, nextPerfectNumber(), which in turn uses the isPerfect() method to find the next perfect number beyond the number passed as the parameter. This method call will take a long time to execute even for small values (especially given how unoptimized this code is); there just aren’t that many perfect numbers.

Using this new version of NumberClassifier, I can create a lazy list of perfect numbers, as shown in Example 4-17.

Example 4-17. Lazily initialized list of perfect numbers
   def perfectNumbers(n) { prepend(n,
      { perfectNumbers(nextPerfectNumberAfter(n)) }) };

    @Test
    public void infinite_perfect_number_sequence() {
        def perfectNumbers = perfectNumbers(nextPerfectNumberAfter(1))
        assertEquals([6, 28, 496], perfectNumbers.getHead(3))
    }

Using the prepend() method I defined in Example 4-15, I construct a list of perfect numbers with the initial value as the head and a closure block that knows how to calculate the next perfect number as the tail. I initialize my list with the first perfect number after 1 (using a static import so that I can call my NumberClassifier.nextPerfectNumberFrom() method more easily), then I ask my list to return the first three perfect numbers.

Calculating new perfect numbers is expensive, so I would rather do it as little as possible. By building it as a lazy list, I can defer calculations until the optimum time.

It is more difficult to think about infinite sequences if your abstraction of “list” is “numbered slots.” Thinking of a list as the “first element” and the “rest of the list” encourages you to think of the elements in the list rather than the structure, which in turn allows you to think about things like lazy lists.

Building a Lazy List

As already mentioned, languages can be categorized as strict (eagerly evaluating all expressions) or lazy (deferring evaluation until absolutely needed). Groovy is a strict language by nature, but I can transform a nonlazy list into a lazy one by recursively wrapping a strict list within a closure. This lets me defer evaluation of subsequent values by delaying execution of the closure block.

A strict empty list in Groovy is represented by an array, using empty square braces: []. If I wrap it in a closure, it becomes a lazy empty list:

{-> [] }

If I need to add an a element to the list, I can add it to the front, then make the entire new list lazy again:

{-> [ a, {-> [] } ] }

The method for adding to the front of the list is traditionally called either prepend or cons. To add more elements, I repeat this operation for each new item; adding three elements (a, b, and c) to the list yields:

{-> [a, {-> [b, {-> [ c, {-> [] } ] } ] } ] }

This syntax is clumsy, but once I understand the principle, I can create a class in Groovy that implements a traditional set of methods for a lazy collection, as shown in Example 4-18.

Example 4-18. Building a lazy list in Groovy
class PLazyList {
  private Closure list

  private PLazyList(list) {
    this.list = list
  }

  static PLazyList nil() {
    new PLazyList({-> []})
  }

  PLazyList cons(head) {
    new PLazyList({-> [head, list]})
  }

  def head() {
    def lst = list.call()
    lst ? lst[0] : null
  }

  def tail() {
    def lst = list.call()
    lst ? new PLazyList(lst.tail()[0]) : nil()
  }

  boolean isEmpty() {
    list.call() == []
  }

  def fold(n, acc, f) {
    n == 0 || isEmpty() ? acc : tail().fold(n - 1, f.call(acc, head()), f)
  }

  def foldAll(acc, f) {
    isEmpty() ? acc : tail().foldAll(f.call(acc, head()), f)
  }

  def take(n) {
    fold(n, []) {acc, item -> acc << item}
  }

  def takeAll() {
    foldAll([]) {acc, item -> acc << item}
  }

  def toList() {
    takeAll()
  }
}

In Example 4-18, the constructor is private; it’s called by starting with an empty list using nil(), which constructs an empty list. The cons() method enables me to add new elements by prepending the passed parameter, then wrapping the result in a closure block.

The next three methods enable list traversal. The head() method returns the first element of the list, and tail() returns the sublist of all elements except the first. In both cases, I call() the closure block—known as forcing the evaluation in lazy terms. Because I’m retrieving values, it ceases to be lazy as I harvest the values. Not surprisingly, the isEmpty() method checks to see if any terms are left to resolve.

The remaining methods are higher-order functions for performing operations on the list. The fold() and foldAll() methods perform the familiar fold operation. I’ve shown the use of this family of methods in previous chapters, but this is the first time I’ve shown a recursive definition written purely in terms of closure blocks. The foldAll() method checks to see if the list is empty and, if it is, returns acc (the accumulator, the seed value for the fold operation). Otherwise, it recursively calls foldAll() on the tail() of the list, passing the accumulator and the head of the list. The function (the f parameter) should accept two parameters and yield a single result; this is the “fold” operation as you fold one element atop the adjacent one.

Example 4-19 shows how to build and manipulate a list.

Example 4-19. Exercising lazy lists
def lazylist = PLazyList.nil().cons(4).cons(3).cons(2).cons(1)
println(lazylist.takeAll())
println(lazylist.foldAll(0, {i, j -> i + j}))
lazylist = PLazyList.nil().cons(1).cons(2).cons(4).cons(8)
println(lazylist.take(2))

In Example 4-19, I create a list by cons()-ing values onto an empty list. Notice that when I takeAll() of the elements, they come back in the reverse order of their addition to the list. Remember, cons() is really shorthand for prepend; it adds elements to the front of the list. The foldAll() method enables me to sum the list by providing a transformation code block, {i, j → i + j}, which uses addition as the fold operation. Last, I use the take() method to force evaluation of only the first two elements.

Real-world lazy-list implementations differ from this one, avoiding recursion and adding more flexible manipulation methods. However, knowing conceptually what’s happening inside the implementation aids understanding and use.

Benefits of Laziness

Lazy lists have several benefits. First, you can use them to create infinite sequences. Because the values aren’t evaluated until needed, you can model infinite lists by using lazy collections, as I illustrated in Example 4-16.

A second benefit is reduced storage size. If—rather than hold an entire collection—I can derive subsequent values, then I can trade storage for execution speed. Choosing to use a lazy collection becomes a trade-off between the expense of storing the values versus calculating new ones.

Third, one of the key benefits of lazy collections is that the runtime can generate more efficient code. Consider the code in Example 4-20.

Example 4-20. Finding palindromes in Groovy
def isPalindrome(s) {
  def sl = s.toLowerCase()
  sl == sl.reverse()
}

def findFirstPalindrome(s) {
  s.tokenize(' ').find {isPalindrome(it)}
}

s1 = "The quick brown fox jumped over anna the dog";
println(findFirstPalindrome(s1))
s2 = "Bob went to Harrah and gambled with Otto and Steve"
println(findFirstPalindrome(s2))

The isPalindrome() method in Example 4-20 normalizes the case of the subject word, then determines if the word has the same characters in reverse. findFirstPalindrome() tries to find the first palindrome in the passed string by using Groovy’s find() method, which accepts a code block as the filtering mechanism.

Suppose I have a huge sequence of characters within which I need to find the first palindrome. During the execution of the findFirstPalindrome() method, the code in Example 4-20 first eagerly tokenizes the entire sequence, creating an intermediate data structure, then issues the find() command. Groovy’s tokenize() method isn’t lazy, so in this case it might build a huge temporary data structure, only to discard most of it. Consider the same code written in Clojure, appearing in Example 4-21.

Example 4-21. Clojure’s palindromes
(defn palindrome? [s]
  (let [sl (.toLowerCase s)]
  (= sl (apply str (reverse sl)))))

(defn find-palindromes [s]
  (filter palindrome? (clojure.string/split s #" ")))

(println (find-palindromes "The quick brown fox jumped over anna the dog"))
; (anna)
(println (find-palindromes "Bob went to Harrah and gambled with Otto and Steve"))
;(Bob Harrah Otto)
(println (take 1 (find-palindromes "Bob went to Harrah with Otto and Steve")))
;(Bob)

The implementation details in Examples 4-20 and 4-21 are the same but use different language constructs. In the Clojure (palindrome? ) function, I make the parameter string lowercase, then check equality with the reversed string. The extra call to apply converts the character sequence returned by reverse back to a String for comparison. The (find-palindromes ) function uses Clojure’s (filter ) function, which accepts a function to act as the filter and the collection to be filtered. For the call to the (palindrome? ) function, Clojure provides several alternatives. I can create an anonymous function to call it as (palindrome? %). When I have a single parameter, Clojure allows me to avoid declaring the anonymous function and naming the parameter, which I substitute with % in the (palindrome? %) function call. In Example 4-21, I can use the even shorter form of the function name directly; (filter ) is expecting a method that accepts a single parameter and returns a Boolean, which matches (palindrome? ).

The translation from Groovy to Clojure entailed more than just syntax. All of Clojure’s data structures are lazy when possible, including operations on collections such as filter and split. Thus, in the Clojure version, everything is automatically lazy, which manifests in the second example in Example 4-21, when I call (find-palindromes ) on the collection with multiples. The return from (filter ) is a lazy collection that is forced as I print it. If I want only the first entry, I must take the number of lazy entrants that I need from the list.

Scala approaches laziness in a slightly different way. Rather than make everything lazy by default, it offers lazy views on collections. Consider the Scala implementation of the palindrome problem in Example 4-22.

Example 4-22. Scala palindromes
def isPalindrome(x: String) = x == x.reverse
def findPalidrome(s: Seq[String]) = s find isPalindrome

findPalindrome(words take 1000000)

In Example 4-22, pulling one million words from the collection via the take method will be quite inefficient, especially if the goal is to find the first palindrome. To convert the words collection to a lazy one, use the view method:

findPalindrome(words.view take 1000000)

The view method allows lazy traversal of the collection, making for more efficient code.

Lazy Field Initialization

Before leaving the subject of laziness, I’ll mention that two languages have a nice facility to make expensive initializations lazy. By prepending lazy onto the val declaration, you can convert fields in Scala from eager to as-needed evaluation:

lazy val x = timeConsumingAndOrSizableComputation()

This is basically syntactic sugar for the code:

var _x = None
def x = if (_x.isDefined) _x.get else {
  _x = Some(timeConsumingAndOrSizableComputation())
  _x.get
}

Groovy has a similar facility using an advanced language feature known as Abstract Syntax Tree (AST) transformations. They enable you to interact with the compiler’s generation of the underlying abstract syntax tree, allowing user transformations at a low level. One of the predefined transformations is the @Lazy attribute, shown in action in Example 4-23.

Example 4-23. Lazy fields in Groovy
class Person {
    @Lazy pets = ['Cat', 'Dog', 'Bird']
}

def p = new Person()
assert !(p.dump().contains('Cat'))

assert p.pets.size() == 3
assert p.dump().contains('Cat')

In Example 4-23, the Person instance p doesn’t appear to have a Cat value until the data structure is accessed the first time. Groovy also allows you to use a closure block to initialize the data structure:

class Person {
    @Lazy List pets = { /* complex computation here */ }()
}

Finally, you can also tell Groovy to use soft references—Java’s version of a pointer reference that can be reclaimed if needed—to hold your lazily initialized field:

class Person {
    @Lazy(soft = true) List pets = ['Cat', 'Dog', 'Bird']
}

This creates the most memory efficient version, with lazy initialization and aggressive reclamation of memory if needed.

Get Functional Thinking now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial