Understanding the Strategy Pattern

Conditionals (if, switch, and match statements) are usually the first 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:

fn count_hailstone_numbers(mut n: u128) -> u128 {
    let mut count = 0;

    while (n > 1) {
        if n % 2 == 0 {
            n = n / 2
        } else {
            n = 3 * n + 1
        }

        count = count + 1
    }

    count
}

function countHailstoneNumbers(n) {
    var count = 0;

    while (n > 1) {
        if (n % 2 === 0) {
            n = n / 2;
        } else {
            n = 3 * n + 1;
        }

        count = count + 1;
    }

    return count;
}

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:

Find the highest number reached in the hailstone sequence,
record each of the numbers in the sequence,
…and count them.

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

struct HailstoneResult {
    count: u128,
    max: u128,
    numbers: Vec<u128>,
}

fn generate_hailstone_numbers(mut n: u128) -> HailstoneResult {
    let mut count = 0;
    let mut max = n;
    let mut numbers = Vec::new();

    while n > 1 {
        n = if n % 2 == 0 { n / 2 } else { 3 * n + 1 };
        count = count + 1;
        max = std::cmp::max(max, n);
        numbers.push(n);        
    }

    HailstoneResult { count, max, numbers }
}

function generateHailstoneNumbers(n) {
    var count = 0;
    var max = 0;
    var numbers = [];

    while (n > 1) {
        n = n % 2 === 0 ? n / 2 : 3 * n + 1;
        count++;
        max = Math.max(max, n);
        numbers.push(n);
    }

    return { count, max, numbers }
}

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.

fn record_hailstone_numbers<'a>(recorder: &'a mut impl Record, mut n: u128) {
    while n > 1 {
        n = if n % 2 == 0 { n / 2 } else { 3 * n + 1 };
        recorder.record(&n);
    }
}

function recordHailstoneNumbers(recorder, n) {
    while (n > 1) {
        n = n % 2 === 0 ? n / 2 : 3 * n + 1;
        recorder.record(n)
    }
}

That seems straightforward enough: it accepts a mutable reference to 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. Note that there are no traits or equivalents in JavaScript, so we’ll use a superclass instead.

trait Record {
    fn record(&mut self, n: &u128);
}

class BaseRecorder {
    constructor() {
        this.state = this.initialValue()
    }

    initialValue() {
        throw 'Not implemented';
    }

    record(n) {
        throw 'Not implemented';
    }
}

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.

trait Report<T> {
    fn report(&self) -> T;
}

class BaseRecorder {
    initialValue() {
        throw 'Not implemented';
    }

    record(n) {
        throw 'Not implemented';
    }

    report() {
        return this.state;
    }
}

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.

#[derive(Default)]
struct HsCounter {
    state: u128,
}

impl Record for HsCounter {
    fn record(&mut self, _: &u128) {
        self.state = self.state + 1
    }
}

impl Report<u128> for HsCounter {
    fn report(&self) -> u128 {
        self.state
    }
}

class HsCounter extends BaseRecorder {
    initialValue {
        return 0;
    }

    record(_) {
        this.count++;
    }
}

Collecting

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

#[derive(Default)]
struct HsList {
    state: Vec<u128>,
}

impl Record for HsList {
    fn record(&mut self, n: &u128) {
        self.state.push(*n)
    }
}

impl Report<Vec<u128>> for HsList {
    fn report(&self) -> Vec<u128> {
        self.state.clone()
    }
}

class HsList {
    initialValue() {
        return [];
    }

    record(n) {
        this.state.push(n);
    }

    report() {
        return this.state;
    }
}

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.”

#[derive(Default)]
struct HsMax {
    state: u128,
}

impl HsMax {    
    fn new(state: u128) -> Self {
        Self { state }
    }
}

impl Record for HsMax {
    fn record(&mut self, n: &u128) {
        self.state = std::cmp::max(self.state, *n)
    }
}

impl Report<u128> for HsMax {
    fn report(&self) -> u128 {
        self.state
    }
}

class HsMax {
    
}

Using the Strategies

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

fn main() -> result::Result<(), Box<dyn error::Error>> {
    let mut counter = HsCounter::default();
    let mut max = HsMax::default();
    let mut list = HsList::default();

    record_hailstone_numbers(&mut counter, 5);
    record_hailstone_numbers(&mut max, 5);
    record_hailstone_numbers(&mut list, 5);

    println!(
        "counter: {}\nmax: {}\nlist: {:?}",
        counter.report(),
        max.report(),
        list.report(),
    );

    Ok(())
}

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.

impl<'a> Record for Vec<&'a mut dyn Record> {
    fn record(&mut self, n: &u128) {
        for record in self {
            record.record(n)
        }
    }
}

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.

fn main() -> result::Result<(), Box<dyn error::Error>> {
    let mut counter = HsCounter::default();
    let mut max = HsMax::default();
    let mut list = HsList::default();

    let mut recorders: Vec<&mut dyn Record> = vec![&mut counter, &mut max, &mut list];
    record_hailstone_numbers(&mut recorders, 5);

    println!(
        "counter: {}\nmax: {}\nlist: {:?}",
        counter.report(),
        max.report(),
        list.report()
    );

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.

#[derive(Default)]
struct HsProgressBar {}

impl Record for HsProgressBar {
    fn record(&mut self, n: &u128) {
        match n {
            1 => println!("."),
            _ => {
                print!(".");
                io::stdout().flush().expect("flushing stdout failed");
            }
        }
    }
}

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?

#[cfg(test)]
mod tests {
    use super::*;

    struct HsTest {
        state: Vec<u128>,
        count: u128,
    }

    impl HsTest {
        fn new(mut state: Vec<u128>) -> Self {
            state.reverse();
            Self { state, count: 0 }
        }

        fn is_empty(&self) -> bool {
            self.state.is_empty()
        }
    }

    impl Record for HsTest {
        fn record(&mut self, n: &u128) {
            self.count = self.count + 1;
            let ex = self.state.pop().expect("too many numbers generated");
            assert_eq!(*n, ex, "step {}: expected {}, not {}", self.count, ex, n)
        }
    }

    #[test]
    fn test_five() {
        let mut expected = HsTest::new(vec![16, 8, 4, 2, 1]);
        record_hailstone_numbers(&mut expected, 5);
        assert!(expected.is_empty())
    }
}

Wrapping it Up

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

In “domain-driven design,” the “repository pattern” usually includes an application of the strategy pattern to data sources.
The ports-and-adapters architecture (or “hexagonal architecture”) relies on the strategy pattern to handle mapping external data to internal business objects.
Application loggers make use of the strategy pattern to allow redirection of logs to external services, files, or streams.
Web frameworks use the strategy pattern to handle serialization to multiple content types, like JSON and XML.

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

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
Use the functions defined here to find out which sequence is the largest for starting numbers less than a billion.
⚙ Can you implement std::format::Display for the strategies as implemented? How, or why not?