data Blog = Blog { me :: Programmer, posts :: [Opinion] }

Understanding the Strategy Pattern

Conditionals (if, switch, and match statements) are usually the first tool programmers reach for when we need to vary the execution of a function. They’re easy to understand and convenient to use, as long as the variations are simple. As software grows, though, extensibility and comprehensibility begin to require that we create ways to “hook” new functionality into our functions. The strategy pattern offers a method to accomplish that:

Define a family of algorithms, encapsulate each one, and make them interchangeable. [The strategy pattern] lets the algorithm vary independently from clients that use it.
— “Strategy Pattern” from the c2.com wiki.

Let’s look at a familiar algorithm and consider how the strategy pattern might be applied to it. We’ll use the “hailstone sequence,” also known as the Collatz sequence:

\begin{equation*} C(n) = \begin{cases} n \div 2, & n\bmod 2 \equiv 0 \\
3n + 1, & n\bmod 2 \equiv 1 \end{cases} \end{equation*}

This formula is probably best known as part of the Collatz conjecture, which is an open problem in mathematics that states that $C(n)$ always ends at one in a finite number of steps. As an example:

\begin{equation*} \begin{aligned} C(5) & = 5 \times 3 + 1 & = 16 \\
C(16) & = 16 \div 2 & = 8 \\
C(8) & = 8 \div 2 & = 4 \\
C(4) & = 4 \div 2 & = 2 \\
C(2) & = 2 \div 2 & = 1 \end{aligned} \end{equation*}

The following function, implemented in Rust, will perform the steps above and counts the number of steps until the sequence terminates at one:

Its procedural approach is straightforward and, for most programmers, is the first style of code they encounter. It’s easy to read, like a flow chart or a recipe. It does have a weakness, though: it isn’t very extensible. For example, what if we want to be able to record the hailstone numbers in different ways? Right now we’re just counting them. We might instead want to:

A first pass at adding this functionality might look like this:

As we add more functionality, we add complexity to the function and its result type. Worse, we can’t mix and match. If we were only interested in finding the longest sequence below a billion, for example, we wouldn’t want to allocate and discard vectors for each number in turn.

A Standard Interface

We first need to define a base type that will govern the interface that we want to use. Let’s write the “consumer” of this interface first so that we can see what we need to do.

That seems straightforward enough: it accepts a recorder and sends it each hailstone number. This version of the function doesn’t have a return value, although it could—it’s independent of the recorder.

Let’s define a trait that can provide this interface.

Next, we’ll need a way to get data out of each strategy. Depending on which strategy we’re using, the data that we receive will vary, so this will need to be generic. Keeping it separate from the Record trait allows us to avoid making record_hailstone_numbers generic as well.

Implementing the Strategies

Counting

We’ll implement the counting functionality using our new trait first. Notice that the argument to record is unused—we’re really just recording the call to HsCounter::record for this strategy.

Collecting

Next, the “List” recorder will collect all of the hailstone numbers generated as part of the sequence.

Finding the Maximum

Last, we’ll keep track of the highest number generated as part of the hailstone sequence. Note that the starting value might be the largest, so we need to add a constructor for this strategy that accepts the starting value as a “seed.”

Using the Strategies

We can then use our new recorders by passing them to record_hailstone_numbers:

The output is:

counter: 5
max: 16
list: [16, 8, 4, 2, 1]

Efficiency Concerns

There’s a serious flaw in this approach compared to the procedural example, though: for each strategy we want to use, we’re calling record_hailstone_numbers again. That’s not a catastrophe here, but if the function called an external service, stored data in the database, or required heavier computation, there would be a serious performance penalty each time we added a strategy. As long as we maintain our Record interface, though, we can create a strategy that composes several others.

We can’t implement the Report<T> trait here, because the entries in the vector could have different T parameters. main will still need to own the strategies and call report() on each individually.

Even though Vec<T> is a foreign type—that is, it’s defined in the standard library instead of our program—this impl means that we can build a list of references to our recorders, then pass it to record_hailstone_numbers once.

Side Effects

All of these strategy implementations have one thing in common: they’re all self-contained. The strategy pattern can also be used for side effects, like writing to a log stream or retrieving data from the database. In our case, let’s display a “progress bar” as we generate hailstone numbers. This strategy doesn’t require us to implement the Report trait, either.

Testing

Don’t overlook the usefulness of the strategy pattern for testing! In a real application, you might want to vary the data source that a method is using, or mock responses from an external service. In our case, we’re modeling a well-known mathematical problem; shouldn’t we be able to check our implementation against expected sequences?

Wrapping it Up

The number of more specific patterns that boil down to an application of the strategy pattern is striking:

Working programmers must deal with code that feels like it has grown by accretion: functions that have side effects you don’t want, are impossible to test, or are simply hard to understand because of the number of things they’re doing. Nothing in is a universal solution, but these situations are often an opportunity to think about extracting some of those parts of the code into a shared “strategy” interface. If you’re working in a less strongly-typed language than Rust, it’s a good idea to reach for a higher-order function in these cases—but always keep in mind the purpose and goals of the strategy pattern to avoid falling into a degenerate form like JavaScript’s “callback hell.”

Exercises

  1. The examples use a static value as the input to the record_hailstone_numbers function. Implement three data sources using the strategy pattern:

    1. Just(n), for a static value
    2. Input, for interactive user input
    3. Random, for a randomly selected number

  2. Use the functions defined here to find out which sequence is the largest for starting numbers less than a billion.

  3. ⚙ Can you implement std::format::Display for the strategies as implemented? How, or why not?