tisdag, november 20, 2007

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?

5 kommentarer:

Bill Six sa...

I usually look to use the Reduce pattern whenever I need to iterate over a collection with an accumulator, and it looks like Ruby uses the "inject" for that.

irb(main):041:0> [1,2,3,4,5].inject([]) do | acc, e |
irb(main):042:1* [e] + acc
irb(main):043:1> end
=> [5, 4, 3, 2, 1]

Mauricio Fernandez sa...

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?

Since Ruby is lacking tail-call optimization, one of the main reasons to use accumulators is gone. It is both more efficient and convenient to use traversal and fold methods defined in the container, which will often be a plain old array or hash. (Ruby adds so much overhead that you rarely create new, generic data structures, and fall back to arrays and hashes at the lowest level.)

There are many things in Ruby that dissuade you from writing functional code in addition to those you mention; to name a few:
* no efficient tuples (at least for 2-3 elements)... therefore, no efficient lists (1.9 is better at that, with up to 3 elements stored inside RSTRUCT slots)
* the core data structures are imperative (a functional map would be very useful at times)
* no pattern matching: you can abuse case expressions or hack something that looks like it, but it's not the same thing. You'd want destructuring assignment for more things than arrays. Which brings us back to the lack of tuples and algebraic types.

In general, in Ruby you want to spend as much time as possible in C code defined in core classes or extensions, so your code will not be more functional than they are.

lysosterol sa...

I don't know if this is a good solution in Ruby but it can be done with standard fold and "cons"

def foldl(l, l0, &b)
if(l.empty?) then l0
else
foldl(l[1,l.length],
b.call(l[0], l0),
&b)
end
end

def reverse(l)
foldl(l, [])
{|car, cdr| [car]+cdr}
end

Jean sa...
Den här kommentaren har tagits bort av skribenten.
Jean Lazarou sa...

[bill six] I wonder if writing your proposal next way wouldn't be more efficient (Ruby should create less temp objects):
def reverse(list)
list.inject([]) {|acc, cur|
acc.insert 0, cur
}
end

Another way to write list reversing would be:
def reverse(list)
Array.new(list.length) { |i|
list[list.length - i - 1]
}
end

And a variation on Ola's third solution
def reverse(list)

block = proc do

def reverse list, i, res
return res if i == -1
res << list[i]
reverse(list, i - 1, res)
end

end

block.instance_eval(&block)

block.reverse list, list.length - 1, []

end