I’m taking a course in Ruby on Rails, and one of the suggested projects is to write a function that will return the class hierarchy for an object. This is a very simple problem, but it got me to thinking. The obvious solution is to use a loop. But Ruby has a whole set of collection-based idioms using block syntax that seem to inherit from Smalltalk. I wondered if I might be able to put those to use.
So I started thinking about this whole class of problems. I wanted a way to express an enumerator where f(n) depends solely on the values of a fixed number of recent values. For instance, in the case of returning the class hierarchy for an object, f(n) depends solely on f(n-1), whereas in the case of generating the Fibonacci sequence, f(n) depends upon f(n-1) and f(n-2). One approach to these sort of problems is to use recursion, although in the case of the Fibonacci sequence, recursion can result in performance issues that can be resolved through the use of Memoization. I wanted to encode the recursive relationship in a non-recursive solution.
So I came up with:
def enumerator_from_generator_simple(*history, &block)
Enumerator.new do |yielder|
history.each { |x| yielder.yield x }
loop do
history = history[1, history.length-1] + [block.call(*history)]
yielder.yield history[-1]
end
end
end
This takes two things – a list of “seed” values for the history and a block. The block will be passed the history and is expected to generate the next value in the sequence. The number of history values to pass to the block is determined by the number of seed values passed initially. With this method in hand, we can then create an enumerator for the Fibonacci sequence and then extract the first 10 values (be very careful not to try to extract all the values – this is the enumerator for an infinite list):
foo = enumerator_from_generator_simple(1, 1) do
|*history|
history[0]+history[1]
end
p foo.first(10)
We can also then write the class hierarchy enumerator:
def get_superclasses(object)
superclass_enum = enumerator_from_generator_simple(object.class) do |old_class|
new_class = old_class.superclass
raise StopIteration if new_class == nil
new_class
end
superclass_enum.to_a
end
p get_superclasses(5)
Note than in this case, I defined the method by having it create a new enumerator using the class of the passed object as the history. I use raise StopIteration to halt the enumeration once we reach a class whose superclass is nil. Voila! No looping, just an expression of the recursive relationship.
My attention then turned to two different areas. The first was adding some performance improvements to the code. These may be a little excessive, but it struck me that the code listed above is a bit inefficient when dealing with some of the most common cases, such as a history of one element. So I wrote the following, which has hand-tweaked code for the most common cases (no elements, one element, and two elements):
def enumerator_from_generator(*history, &block)
if history.length == 0 then
Enumerator.new do |yielder|
loop do
yielder.yield block.call
end
end
elsif history.length == 1 then
history = history[0]
Enumerator.new do |yielder|
yielder.yield history
loop do
history = block.call(history)
yielder.yield history
end
end
elsif history.length == 2 then
history_0 = history[0]
history_1 = history[1]
Enumerator.new do |yielder|
yielder.yield history_0
yielder.yield history_1
loop do
history_0, history_1 = history_1, block.call(history_0, history_1)
yielder.yield history_1
end
end
else
Enumerator.new do |yielder|
history.each { |x| yielder.yield x }
loop do
history = history[1, history.length-1] + [block.call(*history)]
yielder.yield history[-1]
end
end
end
end
With that in hand, I turned to some simple testing. As part of testing, I realized that the Fibonacci sequence is actually a special case of a set of Fibonacci sequences. We’ll call the “traditional” Fibonacci sequence Fib2, where Fib2(n) = Fib2(n-1) + Fib2(n-2). The next one in the set of sequences would be Fib3 = Fib3(n-1) + Fib3(n-2) + Fib3(n-3). And so forth and so on. If one uses history.inject(:+) in place of the explicit addition, it becomes simple to express a whole range of these. Finally, I start generating the enumerator using brace block syntax so I can cram everything on one line.
p ( enumerator_from_generator(1, 1) { |*history| history.inject(:+) } ).first(20)
p ( enumerator_from_generator(1, 1, 1) { |*history| history.inject(:+) } ).first(20)
p ( enumerator_from_generator(1, 1, 1, 1) { |*history| history.inject(:+) } ).first(20)
p ( enumerator_from_generator(1, 1, 1, 1, 1) { |*history| history.inject(:+) } ).first(20)
I just increase the number of elements passed initially and, voila, Fibx!
Then I got to thinking that all of this addition was a little excessive. In the case of two or three elements, it’s not bad. But what if I was computing Fib1000? The vast majority of the addition in each step was done in the previous step. I realized that Fibx(n) = 2 * Fibx(n-1) – Fibx(n-1-x). That is to say, each time the very oldest history element drops off and we add a new Fibx(n-1). But since Fibx(n-1) is equal to the whole sum without the changes, we can just double it and subtract the oldest element. Of course, then we need to keep track of x+1 elements in our history and we need to seed the list with an initial sum, but the following enumerates Fib5 just as well as the last example above:
p ( enumerator_from_generator(1, 1, 1, 1, 1, 5) { |*history| history[-1] * 2 - history[0] } ).first(20)
My final realization was that Fibx(n)/Fibx(n-1) has an asymptotic limit – specifically, if the limit as n goes to infinity of Fibx(n)/Fibx(n-1) is r, then r = 2 – 1 / r^x, which can be recast as r^(x+1) – 2 r^x + 1 = 0. For instance, in the case of Fib2, that is r^3 – 2 r^2 + 1 = 0. There are functions for computing cubic roots, but I’m lazy, so I’ll just take advantage of enumerator_from_generator to write a numeric solver!
p ( enumerator_from_generator(2.0) { |history| 2.0 - 1.0 / (history**2) } ).first(20)
Hey, that converges pretty quickly on the Golden Mean! Which means we’re getting the right answer, since it is well documented that the ratio of consecutive values in the Fibonacci sequence converges on the Golden Mean.
But what if I want to enumerate reasonable converged values for Fibx?
def fibx_ratio(x, iter)
( ( enumerator_from_generator(2.0) { |history| 2.0 - 1.0 / (history**x) } ).first(iter) )[-1]
end
1.upto(10) { |x| p fibx_ratio(x, 100) }
And, as we expect, the ratio for Fibx approaches 2 as x approaches infinity. Which is to say that while Fib2 approximates n^1.618, and Fib3 approximates n^1.839, by the time we get to Fib9 and Fib10, there isn’t much difference between the two functions.
And that, I think, is probably the most I’m going to wring out of this specific suggested project!
