Recursive Sum

In #ruby on Freenode, platzhirsch asked about how to total an array of Transactions when the Transactions may have parents. The two obvious approaches have pitfalls when there are a lot of Transactions, and he said he expects to have 23 million that may be deeply nested. Here’s his sample code:

 
class Transaction
  attr_accessor :amount, :parent
 
  def initialize(amount, parent)
    self.amount = amount
    self.parent = parent
  end
end
 
t1 = Transaction.new(100, nil)
t2 = Transaction.new(250, t1)
t3 = Transaction.new(300, t2)
 
current = t3
all = []
while current != nil
  all << current
  current = current.parent
end
total = all.inject(0) { |total, transaction| total + transaction.amount }

Spoiler warning: last chance to solve it for yourself before I dig into the solutions.

This code sample expressed the first obvious solution: build a list of all the transactions. The problem is that you’ll spend RAM and time building a data structure you expect to use once.

One person offered an addition to Transaction to solve it recursively, the second obvious approach:

 
class Transaction
  def total_amount
    (parent ? parent.total_amount : 0) + amount
  end
end

This pitfall is that this risks blowing the stack when Transactions are deeply nested: recurse too many times and you’ll run out of RAM. It’s also super-specialized, if you want to do anything else with every Transaction you’ll have to write another custom method. And despite the specialization, you might end up writing this logic again if you have a collection of child transactions:

 
t4 = Transaction.new(400, nil)
 
total = [t3, t4].inject(0) { |sum, t| sum + t.amount }

Here’s my approach:

 
# because Transaction doesn't have any logic, I made a shorter version:
Transaction = Struct.new(:amount, :parent)
 
# And I like using powers of two when testing recursion, because the sum
# will come out obviously different for different combinations of items:
t1 = Transaction.new 1, nil
t2 = Transaction.new 2, t1
t3 = Transaction.new 4, t2
t4 = Transaction.new 8, nil
 
TransactionEnumerator = Struct.new(:collection) do
  include Enumerable
 
  def each
    collection.each do |t|
      yield t
      yield t while t = t.parent
    end
  end
end
 
ts = TransactionEnumerator.new [t3, t4]
total = ts.inject(0) { |total, transaction| total + transaction.amount }

This little wrapper doesn’t recurse, doesn’t duplicate Transactions, and doesn’t build a data structure. It can work on any collection of Transactions that exposes each, the sum logic is expressed only once and separately from the control flow, and it provides the powerful Ruby Enumerable interface.

Hope you enjoyed this little puzzle! If you had an alternate solution, please wrap it in <code></code> tags below.

And let me tag on my own fun exercise: add an ID field to Transaction and implement TransactionEnumerator#uniq yield the transactions exactly once, so this returns true (Array has #uniq, but you shouldn’t assume the collection is an Array):

 
TransactionEnumerator.new([t1, t1]).uniq == [t1]

Want more? I'm not as good at forgetting to update @pushcx on Twitter.