Algorithms as objects

By gieseanw

We usually think of an algorithm as a single function with inputs and outputs. Our algorithms textbooks reinforce this notion. They present very concise descriptions that neatly fit in half of a page. This is fine until one actually attempts to implement it as a single function; all the little details add up until you’re left with a gigantic, monolithic function.

That monolithic function lacks readability; it’s so long that you have to scroll for a full minute to get to the end. It’s nested so deeply that you have to scroll horizontally to read it. It’s nigh-impossible to trace the state of a variable that was declared at the top as it mutates every other line.

Because of that, the function also lacks maintainability. Any single line-change has the potential to affect the many lines below it, altering the behavior in unpredictable ways.

Nobody wants to touch this code because it’s such a pain to get any context. There are just too many details. It’s like trying to learn the purpose of an airplane by reading an aerospace engineering textbook.

Complex code requires abstractions. Abstractions help communicate higher level concepts, improving readability and therefore reducing the time to fix bugs or add new features.

A compiler takes code as input and spits out an executable as output. Do you think compilers are implemented as a single monolithic function?

There’s a good chance that your monolithic function should be refactored into one or more classes. It’s okay to implement an algorithm as an object. I encourage it, even.

In this blog post I’ll walk through a handful of code smells that indicate you’ve got a class instead of a function, and then follow it up with code examples demonstrating code that exhibits these code smells. Finally, I’ll demonstrate how we might refactor the offending functions into classes.

How long is too long? Well, Martin Fowler recommends about 10 lines of code, and most experts agree). It’s not that short code is necessarily readable or that long code cannot be readable; it’s just that it tends to be that way. That’s why these are smells not rules.

Personally, I find that 10-20 LOC is more realistic. Professionally, I recommend colleagues (especially ones new to professional software engineering) to keep it at 40 LOC or fewer.

In the end, a good rule of thumb is that no developer should need to scroll to read the entire function. Not even the guy with 32 pt font working on a laptop from the 80s.

Deep nesting is also a cause for concern. In Clean Code, Robert C. Martin recommends one-to-two levels of nesting, and I agree with that assessment. Deeper nesting increases the cognitive complexity score of code, meaning it is subjectively more difficult to understand.

The following section of code is so distinct that I wrote this comment

Banner comments imply there are separate logical blocks in the function that each "do one thing". It’s fine for the algorithm to have separate logical parts, but in a function this is a violation of the single responsibility principle.

These blocks are ripe to pull into helpers, in the form of actual functions or lambdas/closures. The code smell is stronger if any block is suspiciously nested in its own set of curly braces. It’s even stronger if any block is copy-pasted somewhere else.

def foo_bar(): def foo_bar_closure(argument): # ... # end foo_bar_closure closure do_the_thing(foo_bar_closure) # end foo_bar method

When asked to refactor into helper functions, programmers often push back. Their monolithic functions’ logic doesn’t belong outside the algorithm. The logic shouldn’t be outside the algorithm. It would clutter the surrounding code and confuse the client as to what function they should actually call. Those programmers are right!

We need a way to pull the logic out without polluting the global scope. Hmm, how might we achieve that?

Closures are a great way to pass around functionality without "polluting" the global scope, but often they can often be long and complicated to the point where it becomes difficult to remember if you’re reading a closure, or the function in which it resides.

Most helper functions pulled out of an algorithm don’t really make sense to be called by anyone else — they serve some niche role specific to that algorithm. Even a single helper function at the same scope as the main algorithm can lead to confusion; clients now need to spend a few extra seconds considering which function they should actually call. This code smell indicates suboptimal discoverability in your API.

Plus, functions at the same scope as your main algorithm need to be unit tested, which nobody wants to do. Nobody wants to do it because it feels wrong. It is wrong. It would be testing an implementation instead of an interface. We need a way to hide those implementation details elsewhere.

When we refactor our long vertical functions into helpers, we are apt to end up with wide horizontal parameter lists. These parameters represent the state of the algorithm.

Long parameter lists are difficult enough to wrangle as-is; the more parameters a function has, the more difficult it is to properly unit test. This is because the parameter space grows exponentially with each additional parameter. More dimensions (parameters) to test leads to combinatorial explosion of unit tests, making it eventually impossible to adequately cover all possible combinations of values.

Long parameter lists also impart a higher cognitive burden on the caller. The caller needs to remember not only what parameters are available, but also what order they need to be provided (in languages that traditionally only have positional arguments, like C and C++).

I’ve got 99 problems, give me two more

Free-floating helper functions don’t just tend towards long parameter lists. They tend to repeat the same parameters. This copy paste programming hurts readability (what’s different between them?) and is the source of subtle errors (oops, forgot to change the type of that parameter after pasting it!).

green snake
Photo by Marius Masalar on Unsplash

If you spend a little time considering how to address each of the code smells in the above section, you will reach the same conclusion I have: use a class! Refactoring a monolithic algorithm into a class improves readability, which is is our #1 goal.

High readability leads to ease of maintenance, and functionality that is easily maintained means dollars saved in the long run. It’s well known in the industry at this point that the cost of writing code is really measured by the time spent maintaining it down the line.

Code is generally "write once, read many", so the upfront time spent writing the initial code implementation might as well be zero. Time spent "doing it right" means less money spent down the line "getting it right".

Let’s summarize how writing an algorithm as an object helps us, in no particular order:

1. Managed complexity through helper functions and member variables

With a class, you are free to write as many helper functions as you want without fear of polluting the global scope. Having member variables allows a reduction in function parameters. We’ve increased readability and maintainability via encapsulation.

Your algorithm class will have a single public function (except for a constructor) like Run. It’s impossible for a client to call the wrong function; there’s only one way of doing things.

my_algorithm = MyAlgorithmClass()
results =

I chose the coiled-snake image above because it embodies this principle. The snake has pulled itself (helper functions) close, with only its head (entry point) poking out. (Also, I’ll be using Python for most of my code examples.)

An additional benefit is that a single point of entry leaves you with a very predictable API, so long as the entry points are named consistently. I use variations of Run throughout this article, but use whatever makes you comfortable.

A class is at least as testable as its monolothic function counterpart. If you decide that you wish to test other parts of the functionality, well, it’s already modularized enough to pull into another class or standalone utility function.

This modularization lends itself very well to mocking; certain helper functions may instead become abstract/virtual methods on an interface class.

The number of parameters in an algorithm tends to grow over time. This often leads to confusion on the caller’s side. What order should the parameters be passed in?

You don’t want to accidentally swap an X axis value with a Y axis value. Named parameters help a lot, and there are ways to simulate them in languages without native support, but a class gives us another option: Martin Fowler’s Fluent Interface pattern.

AlgorithmClass().WithXValue(10.0) .WithYValue(20.0) .WithEtc(...) .Run();

The above API makes the association between algorithm parameters and their values very obvious. Parameters with default values do not need their With... functions called, and parameters that have required values get checked by the Run function to ensure they received a value (or they’re specified in the constructor).

Note that you may use a builder pattern alongside the fluent interface pattern to create an algorithm-builder as a means of preserving the "single point of entry" benefit I outlined earlier:

AlgorithmClass my_algorithm = AlgorithmClassBuilder() .WithXValue(10.0) .WithYValue(20.0) .WithEtc(...) .Build(); // perform validation of parameters

Algorithms as objects is really just the Command pattern in a new light. It was unintentional, but now that we’ve separated the initialization of the algorithm with the running of the algorithm, we can do either whenever we want.

(The Gang of Four classifies the Command pattern as a behavioral pattern, but note that here we’re actually using it as a structural pattern!)

This delayed callability opens the door to even more refactoring. Perhaps our parameters are inferred via other computations that we’d not prefer to have all in one place. We can set up an algorithm-initialization pipeline, where each stage computes another parameter until the last one executes the algorithm:

AlgorithmClass myAlgorithm;
// .. some processing
// ... more processing

My first and favorite example is one that most programmers have seen and written themselves before: In-order binary tree traversal.

Recall that In-order traversal visits a tree recursively in the following order:

  • left subtree
  • root
  • right subtree

You would use an in-order traversal to print a binary search tree in sorted order, for example.

Let’s define a node class for our tree: BinaryTreeNode (Python):

class BinaryTreeNode(object): def __init__(self, value): self.left = None self.value = value self.right = None # end __init__ built-in
# end BinaryTreeNode class

BinaryTreeNode.value is whatever you want to store in your nodes. For the sake of argument, let’s pretend it is always an int.

Now let’s implement our inorder_traversal algorithm:

def inorder_traversal(root): if not root: # base case return inorder_traversal(root.left) print(root.value) inorder_traversal(root.right)
# end inorder_traversal class

5 lines, 1 parameter, 1 level of nesting. I’d call that pretty clean, and I hope you’d agree.

A bit more difficult

Let’s make things only slightly more complicated. Instead of printing the elements as we go, we need to store them in a list, and then return the list.

Can we do this easily with just one function? Sure, we could make a list per call and then append to it with the result of the recursive functions.

def inorder_traversal(root): values = [] if not root: # base case return values values.extend(inorder_traversal(root.left)) values.append(root.value) values.extend(inorder_traversal(root.right)) return values
# end inorder_traversal function

Not bad, but we’re making a lot of lists, which could hurt our performance as the tree grows. Is there any way we could just append to the same one?

I guess we could pass a list as an optional argument that the client shouldn’t provide:

# values is reserved for the impl, don't use it!
def inorder_traversal(root, values=None): if values is None: values = [] if not root: # base case return values inorder_traversal(root.left, values) values.append(root.value) inorder_traversal(root.right, values) return values # unused by each recursive call
# end inorder_traversal function

This is an abomination. Ripley would dutifully apply the flamethrower to it if she ever saw it, because it screams "kill me".

That values parameter that the client isn’t supposed to call only confuses the API. It also prevents you from making any real guarantees about the algorithm’s correctness without a lot of (unnecessary) boilerplate. Finally, both recursive cases are ignoring their return values, which may leave future maintainers scratching their heads.

To implement the algorithm a bit better, we’d write an "entry function" that will call our recursive "helper function" with a list like so:

# this function is reserved for the impl, don't call it!
def inorder_traversal_helper(root, values): if not root: # base case return inorder_traversal_helper(root.left, values) values.append(root.value) inorder_traversal_helper(root.right, values)
# end inorder_traversal_helper function def inorder_traversal(root): values = [] inorder_traversal_helper(root, values) return values
# end inorder_traversal function

At least the function that the client is supposed to call doesn’t need a values parameter. The individual functions also have a maximum length of 5 LOC.

However, along the way we violated code smells #4 and #5. We have a helper function that shouldn’t be called by anyone but us, and we’re passing state to it.

When we refactor into a class, it all suddenly makes sense.

class InorderTraversalAlgorithm(object): def __init__(self): self.values = [] # end init built-in def run(self, root): self._run_helper(root) return self.values # end run method # the prefix underscore on a member function is a Python convention for "private" functions def _run_helper(self, root): if not root: # base case return self._run_helper(root.left) # recursive case 1 self.values.append(root.value) self._run_helper(root.right) # recursive case 2 # end _run_helper method
# end class InorderTraversalAlgorithm

Which you could then call like so:

result = InorderTraversalAlgorithm().run(some_root)

If you find you don’t like making the client construct an object and call a run() method, you can use a technique called trampolining to hide that:

def inorder_traversal(some_root): return InorderTraversalAlgorithm().run(some_root) # ...
result = inorder_traversal(some_root)

Wow! That code doesn’t smell at all. In fact, it smells great! (Apologies to the anosmiacs reading this.)

Now that you’ve seen it in action, you’ll notice that every recursive algorithm with state can be implemented in this way.

Some languages provide facilities for making classes themselves callable, so you can ditch the run name. In Python this is achieve by implementing the __call__ method on your class. In C++, you would overload the function call operator operator(). You’d probably still want to trampoline the call, though, because the result looks something like this:

result = InorderTraversalAlgorithm()(some_root)

Some functions that you extricate from your monolith may be really generic. These functions can, and should live apart from the algorithm class.

For example, let’s revisit the difference between the in-order traversal implementation for printing, and the one for writing to a list:

def inorder_traversal(root): if not root: # base case return inorder_traversal(root.left) # recursive case 1 print(root.value) inorder_traversal(root.right) # recursive case 2
# end inorder_traversal function
# ...InorderTraversalAlgorithm class
def _run_helper(self, root): if not root: # base case return self._run_helper(root.left) self.values.append(root.value) self._run_helper(root.right)
# end _run_helper method

The only discernible difference between these two implementations is that one calls print(root.value) and the other calls self.values.append(root.value)

More generically, we’re just applying a unary function to the value at each node in an in-order traversal fashion. Generic programming aficionados will be quick to create a single function that can be used to do both things:

def apply_inorder_traversal(root, unary_fn): if not root: # base case return apply_inorder_traversal(root.left, unary_fn) unary_fn(root.value) apply_inorder_traversal(root.right, unary_fn)
# end apply_inorder_traversal method

Now we can re-implement both algorithms in terms of this generic one:

def print_inorder_traversal(root): apply_inorder_traversal(root, print)
# end print_inorder_traversal algorithm def inorder_traversal_as_list(root): values = [] def store_next(value): values.append(value) apply_inorder_traversal(root, store_next) return values
# end inorder_traversal_as_list algorithm

(Note that we could have passed values.append directly in Python instead of defining store_next, but most languages are not this flexible, so I didn’t do it here).

A higher-order function arises

When we refactor like this, we are in fact creating a version of the well-defined higher order Map function. Passing a callable to our generic function is okay; it’s user-provided, used by each recursive call, and the resulting overall function is short enough.

If you’re only struggling with code smell #4 (There are actual helper functions, but they shouldn’t be called by anyone else), and not code smell #5 (You’re passing state between your helper functions), then you may decide that it makes more sense for the functions to exist in a helper namespace rather than a proper class.

For example, in C++, our "entry point" and "helper" methods for a traversal might look like this:

namespace inorder_detail{ void inorder_traversal_helper(BinaryTreeNode* root, std::vector<int>& values) { if(!root) // base case return inorder_traversal_helper(root->left, values); // recursive case 1 values.push_pack(root->value); inorder_traversal_helper(root->right, values); // recursive case 2 }
} // inorder_detail namespace std::vector<int> inorder_traversal(BinaryTreeNode* root)
{ std::vector<int> values; inorder_detail::inorder_traversal_helper(root, values); return values;

You may have N functions in your inorder_detail namespace, with a single clear entry point outside. The client only concerns themselves with the entry point that exists outside the namespace (it’s convention to name a namespace <something>_detail to indicate it’s intended to only be used by algorithm implementers, and perhaps knowledgeable power users). This is an effective use of the Facade pattern.

I wouldn’t really recommend the Facade approach unless you have a use case for a power user needing to call one of the implementation-detail functions, or you have distilled additional helper classes to support your algorithm.

I see this one a lot. Someone is tasked with importing data into the system, so they write a monolithic function to do it.

Example average precipitation graph

Let’s pretend that we’re trying to understand the amount of rainfall per day an area receives in a year. Conveniently, there are rain gauges already installed in said area. These gauges will report water accumulation once a day, but only after every 1 unit of water received (the actual unit is not important). This means that there may be days without any data reported.

So we receive a file that looks like this

0 1
1 3
2 1
5 5
... etc ...

We’re interested in a report that looks like this:

0 1
1 3
2 1
3 0
4 0
5 5
... etc...

The report writers want you to provide day/water information in the form of a list of tuples like so:

[(0,1), (1, 3), (2, 1), (3,0), (4, 0), (5, 5)]

The tricky part is that we need to recognize when we’ve missed a day, and fill in a 0 for the missing data.

Here’s a not-unreasonable implementation (sans validation or error checking):

def water_per_day(filename): to_return = [] # ...

We’ll want to use a context manager to nicely close our file object:

 with open(filename) as fin:

Next, we should discard the first line in the file, because it contains the column headers DAY AMOUNT

 # discard column headers fin.readline()

And then we can start iterating over the rest of the lines to get data:

 for line in fin: data = [int(val) for val in line.split()] next_day = data[0] water_amt = data[1]

Now that we’ve read a day and an amount of water for that day, we need to make sure to fill in any missing days with zeros:

 # make sure that any missed day gets a 0 expected_day = 0 if not to_return else to_return[-1][0] + 1 days_diff = next_day - expected_day for day in range(expected_day, expected_day + days_diff): to_return.append((day, 0))

Then we can add the parsed data to our growing collection:

 to_return.append((next_day, water_amt))

Finally we can end the function:

 return to_return
# end water_per_day method
def water_per_day(filename): to_return = [] with open(filename) as fin: # discard column headers fin.readline() for line in fin: data = [int(val) for val in line.split()] next_day = data[0] water_amt = data[1] # make sure that any missed day gets a 0 expected_day = 0 if not to_return else to_return[-1][0] + 1 days_diff = next_day - expected_day for day in range(expected_day, expected_day + days_diff): to_return.append((day, 0)) to_return.append((next_day, water_amt)) return to_return
# end water_per_day method

17 lines of code, and 3 levels of nesting* just for that simple example? Imagine if we needed to validate any of our input, or verify that the file argument we received referred to an actual file? What if lines in the input could contain comments? We’re at bare-bones simple, and it’s already this long and complicated.

(*we could have reduced our innermost for loop to to_return.extend([0 for day in range(<etc>)]), but I left it as-is for teaching and because most languages would require a loop here; Python’s comprehensions feel like cheating sometimes).

Our implementation violates code smells #1 and #2

  • it’s too long or too deeply nested, and
  • Banner comments (# make sure that any missed day gets a 0)

So lets refactor.

Let’s pull the missed-day calculation into a closure so that everything remains part of the same function.

def water_per_day(filename): to_return = [] def add_zeros_for_missing_days(next_day): expected_day = 0 if not to_return else to_return[-1][0] + 1 days_diff = next_day - expected_day for day in range(expected_day, expected_day + days_diff): to_return.append((day, 0)) with open(filename) as fin: # discard column headers fin.readline() for line in fin: data = [int(val) for val in line.split()] next_day = data[0] water_amt = data[1] add_zeros_for_missing_days(next_day) to_return.append((next_day, water_amt)) return to_return
# end water_per_day function

Our new closure add_zeros_for_missing_days does a good job of separating responsibility inside our function and it reduces our nesting from three to two.

On the other hand, we actually increased our overall lines of code to 17. We’re now violating code smell #3 (Helper functions as nested closures, but it’s still too long).

So let’s refactor some more.

Because our function didn’t get any simpler thanks to our closure, we decide to see what moving it into its own function does:

def add_zeros_for_missing_days(next_day, to_return): expected_day = 0 if not to_return else to_return[-1][0] + 1 days_diff = next_day - expected_day for day in range(expected_day, expected_day + days_diff): to_return.append((day, 0))
# end add_zeros_for_missing_days helper function def water_per_day(filename): to_return = [] with open(filename) as fin: # discard column headers fin.readline() for line in fin: data = [int(val) for val in line.split()] next_day = data[0] water_amt = data[1] add_zeros_for_missing_days(next_day, to_return) to_return.append((next_day, water_amt)) return to_return
# end water_per_day function

That’s a bit better — our longest function is now only 10 lines, and our maximum nesting remains at two.

But, we’ve violated both code smells #4 and #5:

  • There are actual helper functions, but they shouldn’t be called by anyone else, and
  • You’re passing state between these helper functions

What does the function add_zeros_for_missing_days even mean if not used in the context of water_per_day?

The function also makes some pretty strong assumptions about the contents of the to_return parameter. Let’s just call the to_return parameter what it is; state for the algorithm.

At this point, we should realize that a class helps us organize our logic better.

When we refactor our algorithm into an object, we will immediately notice how simple and compartmentalized everything can become:

class WaterPerDay(object): def __init__(self): self.water_per_days = [] # end init built-in # entry point def run(self, filename): with open(filename) as fin: self._discard_header(fin) self._parse_columns(fin) return list(self.water_per_days) # end run method def _discard_header(self, fin): # potentially validate the line to ensure it was a valid header fin.readline() # end _discard_header method def _parse_columns(self, fin): for line in fin: data = [int(val) for val in line.split()] next_day = data[0] water_amt = data[1] self._add_zeros_for_missing_days(next_day) self.water_per_days.append((next_day, water_amt)) # end _parse_columns method def _add_zeros_for_missing_days(self, next_day): expected_day = 0 if not self.water_per_days else self.water_per_days[-1][0] + 1 days_diff = next_day - expected_day for day in range(expected_day, expected_day + days_diff): self.water_per_days.append((day, 0)) # end _add_zeros_for_missing_days method
# end class WaterPerDay

Within our class, the longest method is six lines. We’ve moved our list to a class member variable so that it may become an implicit parameter in all functions. There is a single, obvious entry point to our algorithm.

We can test it exactly like before, but if we really wanted to, we could also write unit tests that examined how well we handled malformed column data or missing column headers. Our discard_header method doesn’t actually need a file object, just something that acts like one. This is prime material for a mock object that will return canned data when we read from it.

(Taking the filesystem out of unit tests is a powerful benefit. Not only will it make your tests run faster, but it reduces or removes data dependencies between tests.)

Yes, the class code is longer than our original monolithic method, and this will tend to hold true each time you refactor in this manner. Additional function declarations, and the accompanying whitespace tends to add up. But lines of code is not really our goal; our goal is readability.

(Robert Martin produces a similar effect in Clean Code p. 141 when demonstrating a refactoring example from Donald Knuth for printing prime numbers).

Our class has distinct levels of abstraction, better per-abstraction readability, separation of responsibility, better testability, and overall better maintainability. No single level of abstraction will cause you to scroll your screen horizontally or up-and-down (unlike this monolithic blog post).

Once you get started creating these helpers to manage complexity, you’ll get hooked! You might even already be thinking of ways to simplify the helper functions in our toy example above!

Don’t be surprised when refactoring your algorithm yields more than one object, or even an object that itself needs more helper objects. This is only natural as you break up those 1000 LOC legacy functions.

(Organizing all those resulting objects is an architectural discussion outside the scope of this article, but I can recommend Robert C. Martin’s book Clean Architecture to get started.)

I often witness a lot of initial resistance to the algorithms as objects pattern, but then never again afterwards. Programmers see for themselves that the resulting code is easier to reason about, better organized, and more ergonomic for the end user. So the next time you’re staring down a wall of code, consider a class!


I need to acknowledge Dr. Stephanie Valentine, for ultimately pushing me to write this article as well lending her fantastic editing skills to it. Also, Adam Fidel, for being a great sounding board (and for listening to me monologue for an eternity). Finally, Jason Humber, for helping me find the right balance of Python features so that beginners could still follow along and experts wouldn’t be too appalled. I’m eternally grateful to those who help me continue to grow as a programmer and writer.