How to approach a reduce problem

Ruby’s reduce (aka inject) can be intimidating. It can be hard to both read and to write. This handy two-step approach has helped me write reduce code without tying my brain in knots.

Two-step process

Here are the two steps:

Figure out how to combine 2 items
Use reduce to scale up to n items

They derive from a helpful mental model I have:

reduce is a tool for scaling a method that combines 2 items into a method that combines n items.

Problem: Aggregating T-shirt inventory

Consider some code that models multiple warehouses that hold inventory of various sized t-shirts. We might want to find the total inventory across all warehouses. Aggregation problems commonly call for #reduce but this one could get rather gnarly.

Warehouse = Struct.new(:name, :stock)

warehouses = [
  Warehouse.new("East", {small: 1}),
  Warehouse.new("West", {small: 1, medium: 2, large: 1})
]

Step 1 - figure out how to combine two values

The first step is to make the problem smaller. Don’t try to figure out how to aggregate a whole list of inventories. Instead let’s start by writing a method to sum two inventories.

Because inventories are hashes, we can use Hash#merge to combine them. We use the block form to decide what to do when both hashes contain the same key (e.g. both have an entry for :small). Here we want to add them.

def add_inventories(inventory1, inventory2)
  inventory1.merge(inventory2) do |key, val1, val2|
    val1 + val2
  end
end

Step 2 - use `reduce` to scale operation to n items

Now that we have a way to add two inventories, we can use #reduce to apply our add_inventories method to a whole array. Job done!

warehouses.reduce({}) do |running_total, warehouse|
  add_inventories(running_total, warehouse.stock)
end

Bonus points: extract value object

For extra niceness we could replace our hash of t-shirt sizes with a proper Inventory object. Now we have a place for that add_inventories object to live (that suffix was probably a big hint!) and we can even name it +.

Inventory = Data.define(:small, :medium, :large) do
  def self.empty
    new(small: 0, medium: 0, large: 0)
  end

  def +(other)
    Inventory.new(
      small: self.small + other.small,
      medium: self.medium + other.medium,
      large: self.large + other.large
    )
  end
end

And now the scary block entirely disappears (see this article for how the non-block form works)!

warehouses.map(&:stock).reduce(:+)

Similar patterns: Monoids and Semigroups

This way of thinking is similar to two concepts from abstract algebra: semigroups and monoids. The core idea (slightly oversimplified) is that you have an object that:

Defines a combining method (e.g. Inventory#+) that combines two instances. This method must be order-independent (e.g. a + (b + c) == (a + b) + c). Notice that this is basically my step 1 above!

Defines an “empty” or “neutral” value (e.g. Inventory.empty) that does nothing when combined with another instance using the combining method defined above. For example adding an empty inventory to an existing one is the same as doing nothing some_inventory + Inventory.empty == some_inventory.

It turns out that arrays of these kinds of objects are inherently reduceable. You plug in the empty value as the base case and pass a symbol for the combining method and it all just works!

array_of_monoids.reduce(YourMonoidalObject.empty, :combine)