Modding Out Bob

Meet Bob. Bob works in a warehouse gathering items to ship out for fulfillment of online orders. Customers hate to pay for extra shipping, so companies like Bob’s often group items going to the same destination together into the same box to save on shipping costs. The criteria for grouping sound simple: an item can only be placed in a box with another item if both items are going to the same destination. Whether Bob realizes it or not, he is performing an equivalence relation to the shipping orders he fills.

How might this concept look if we wrote a program to help Bob with his shipping? Conceptually we would need a class to represent each item in a shipping order. This class would need to hold at the very least the information that is necessary for us to determine its equivalence to other items of this class. This will serve as our equivalence class. Next, we would need a method to compare the attributes of an item to another item. This will serve as our equivalence relation. When we compare these classes against each other using the equivalence relation for the purposes of determining groupings, this approach is known as modding out.

A more exact definition of an equivalence class: Given a set X and an equivalence relation (say ~) on X, the equivalence class of an element x in X is the subset of all elements in X which are equivalent to x (Taken from: http://en.wikipedia.org/wiki/Equivalence_class). Let’s start with the class representing an item for shipping:

class Item
  attr_accessor :destination

  def initialize(destination)
    self.destination = destination
  end
end

Item.new("ACME Corporation") # => #<Item:0x998e4b0 @destination="ACME Corporation">

The destination attribute of the class Item is all we need to determine if another item can be shipped with this item. In the real world, the attributes needed for comparison would need to be more specific than just a company name. An implementation might include multiple attributes such as all the parts of an address field, and a customer’s name. Now, we will add an equivalence method to compare this Item against another Item:

class Item
  attr_accessor :destination

  def initialize(destination)
    self.destination = destination
  end

  # This is the equivalence relation
  def ~(other)
    self.destination == other.destination
  end
end

item_a = Item.new("ACME Corporation") # => #<Item:0x998e4b0 @destination="ACME Corporation">
item_b = Item.new("ACME Corporation") # => #<Item:0x998e4b1 @destination="ACME Corporation">
item_c = Item.new("Umbrella Corporation") # => #<Item:0x998e4b3 @destination="Umbrella Corporation">
item_a.~(item_b) # => true
item_a.~(item_c) # => false

Now that we get a Boolean result from our equivalence relation, it is time to use Array#reduce to determine item memberships for a shipping order based on our equivalence class:

def group_items(*items)
  items.reduce([]) do |groupings, item|
    match = groupings.detect { |group| group[0].~(item) }
    match ? match.push(item) : groupings.push([item])
    groupings
  end
end

group_items(item_a, item_b, item_c) # => [[a, b], [c]]

Now for an explanation:

  • We call group_items passing in a collection if Item instances
  • #reduce (or #inject) iterates over this collection, and passes the groupings made so far, and the next item in the items array to a block.
  • #detect is called for each grouping of items. In each group, the first member is fetched, and the equivalence relation is called taking the new item as its argument.
  • If the item is equivalent to a member in a grouping, it is appended to this grouping’s elements. If however, the item is not equivalent to a member in any groupings, a new grouping containing this item as an element is created instead.
  • As the block ends, we return groupings to be passed into the next iteration as the block variable groupings.

Note: The equivalence relation ~ is called O(n^2) times. This means that the comparison needs to be very efficient. If you are making a database call here, it should probably be cached at initialization, instead of on each comparison.

The scenarios in which you would use this pattern are almost countless. Here are a few more examples of real-world equivalence class applications:

  • Grouping the bills on your desk by paid or unpaid
  • Sorting your clean silverware back in the drawer
  • Selecting which errands to run by which side of town you will be on
  • Bagging your groceries by frozen, refrigerated, or dry foods
  • Merging duplicate contacts in your phone’s address book

More information on the equivalence class, and modding out can be found at:

—Ben Simpson