Accumulators in Ruby

So, me and Ben Butler-Cole discussed the fact that accumulators in Ruby isn't really done in the obvious way. This is due to the somewhat annoying feature of Ruby that nested method definitions with the def-keyword isn't lexically scoped, so you can't implement an internal accumulator like you would in Python, Lisp, Haskell or any other languages like that.

I've seen three different ways to handle this in Ruby code. To illustrate, let's take the classic example of reversing a list. The functional way of doing this is to define an internal accumulator, this takes care of making the implementation tail recursive, and very efficient on linked list.

So, the task is to reverse a list in a functional, recursive approach. First version, using optional arguments:

class Reverser
def reverse(list, index = list.length-1, result = [])
 return result if index == -1
 result << list[index]
 reverse(list, index - 1, result)
end
end

So, this one uses two default arguments, which makes it very easy to reuse the same method in the recursive case. The problem here is that the optional arguments expose an implementation detail which the caller really has no need of knowing. The implementation is simple but it puts more burden on the caller. This is also the pattern I see in most places in Ruby code. From a design perspective it's not really that great.

So, the next solution is to just define a private accumulator method:

class Reverser
def reverse(list)
  reverse_accumulator(list, list.length-1, [])
end

private
def reverse_accumulator(list, index, result)
  return result if index == -1
  result << list[index]
  reverse_accumulator(list, index - 1, result)
end
end

This is probably in many cases the preferable solution. It makes the interface easier, but adds to the class namespace. To be sure, the responsibility for the implementation of an algorithm should ideally belong at the same place. With this solution you might have it spread out all over the place. Which brings us to the original problem - you can't define lexically scoped methods within another method. So, in the third solution I make use of the fact that you can actually have recursive block invocations:

class Reverser
 def reverse(list)
   (rec = lambda do |index, result|
      return result if index == -1
      result << list[index]
      rec[index - 1, result]
    end)[list.length-1, []]
 end
end

The good thing about this implementation is that we avoid the added burden of both a divided implementation and an exposed implementation. It might seem a bit more complex to read if you're not familiar with the pattern. Remember that [] is an alias for the call method on Procs. Also, since the assignment to rec happens in a static scope we can actually refer to it from inside the block and get the right value. Finally, all assignments return the assigned value which means that we can just enclose everything in parens and apply it directly. Another neat aspect of this is that since the block is a closure, we don't need to pass the list variable around anymore.

Does anyone have a better solution on how to handle this? Accumulators aren't really that common in Ruby - is this a result of Ruby making functional programming unneat, or is it just don't needed?