An Infinite List of Fibonacci Numbers in Ruby

So I was reading through the Haskell Prelude when I stumbled across `scanl' as a kind of abstraction over `foldl'. I stared, and thought, and stared some more, and couldn’t come up with a use for it; a quick Web search revealed exactly one use: Fibonacci numbers.

(In retrospect: duh.)

So here are all the Fibonacci numbers in Haskell:

fibs = 0 : scanl (+) 1 fibs

As you can see this makes use of infinite, recursive lists. So I wrote this in Ruby.

First I needed infinite lists:

class LazyEmpty
  def empty?
    true
  end
end

class LazyCons
  attr_reader :first

  def initialize(first, &rest)
    @first = first
    @rest = rest
    @rest_called = false
  end

  def rest
    if @rest_called
      @rest
    else
      @rest_called = true
      @rest = @rest.call
    end
  end

  def empty?
    false
  end
end

And now that I have such a thing, I need behavior on it. For example, #take will produce the first n elements of such a list:

class LazyEmpty
  def take(n)
    LazyEmpty.new
  end
end
class LazyCons
  def take(n)
    if n < 0
      self
    elsif n.zero?
      &#91;self.first&#93;
    else
      self.rest.take(n-1) + &#91;self.first&#93;
    end
  end
end
&#91;/code&#93;

So now I can get at the elements:

&#91;code language="ruby"&#93;
irb(main):001:0> l = LazyCons.new(1) { LazyCons.new(2) { LazyCons.new(3) { LazyCons.new(4) { LazyEmpty.new }}}}
=> #<LazyCons:0x7f656ee21208 @rest_called=false, @rest=#<Proc:0x00007f656ee212a8@(irb):2>, @first=1>
irb(main):002:0> l.take(2)
=> [3, 2, 1]

To get the most fun definition for the list of Fibonacci numbers I need #scanl:

class LazyEmpty
  def scanl(q, &f)
    LazyCons.new(q) { LazyEmpty.new }
  end
end

class LazyCons
  def scanl(q, &f)
    LazyCons.new(q) { self.rest.scanl(f.call(q, self.first), &f) }
  end
end

So now I have all the parts needed:

def fibs
  LazyCons.new(0) { fibs.scanl(1) {|x,y| x + y} }
end

See?

irb(main):008:0> fibs.take(10)
=> [55, 34, 21, 13, 8, 5, 3, 2, 1, 1, 0]

That is to say, the nth Fibonacci number is the first element from take(n).

def fib(n)
  fibs.take(n).first
end

At this point I wondered how it performed, especially against the naïve implementation. So I used Benchmark.rb and ruby-prof to compare #fib_naive, #fib_tail (the tail-call rewrite of the naïve implementation), #fib_while (the while loop rewrite of the tail-call rewrite), and #fib_inf_list (as defined above) … and the infinite list was not in last place!

       user       system      total        real
naive 12.020000   2.140000  14.160000 ( 14.174045)
tail   0.000000   0.000000   0.000000 (  0.010399)
while  0.020000   0.000000   0.020000 (  0.008730)
inf    3.360000   0.150000   3.510000 (  3.513216)

naive memory:
Thread ID: 70118283774380
Total: 970.630000

 %self     total     self     wait    child    calls  name
  5.11    970.63    49.61     0.00   921.02 17710000  Object#fib_naive-1 (fib_benchmarks.rb:6}
  1.01      9.79     9.79     0.00     0.00 17710000  Fixnum#- (ruby_runtime:0}
  0.94      9.16     9.16     0.00     0.00 17710500  Fixnum#< (ruby_runtime:0}
  0.53      5.17     5.17     0.00     0.00  8855000  Fixnum#+ (ruby_runtime:0}
  0.00     73.73     0.00     0.00    73.73        1  Integer#times (ruby_runtime:0}
  0.00     73.73     0.00     0.00    73.73      500  Proc#call (ruby_runtime:0}
  0.00     73.73     0.00     0.00    73.73      500  Object#fib_naive (fib_benchmarks.rb:6}
  0.00     73.73     0.00     0.00    73.73        1  Object#profile (fib_benchmarks.rb:48}


tail memory:
Thread ID: 70118283774380
Total: 0.630000

 %self     total     self     wait    child    calls  name
  6.35      0.63     0.04     0.00     0.59    10500  Object#fib_tail_aux-1 (fib_benchmarks.rb:18}
  1.59      0.01     0.01     0.00     0.00    10500  Fixnum#+ (ruby_runtime:0}
  0.00      0.00     0.00     0.00     0.00    10500  Fixnum#- (ruby_runtime:0}
  0.00      0.05     0.00     0.00     0.05      500  Object#fib_tail_aux (fib_benchmarks.rb:18}
  0.00      0.05     0.00     0.00     0.05      500  Object#fib_tail (fib_benchmarks.rb:14}
  0.00      0.05     0.00     0.00     0.05        1  Integer#times (ruby_runtime:0}
  0.00      0.00     0.00     0.00     0.00    11000  Fixnum#zero? (ruby_runtime:0}
  0.00      0.05     0.00     0.00     0.05        1  Object#profile (fib_benchmarks.rb:48}
  0.00      0.05     0.00     0.00     0.05      500  Proc#call (ruby_runtime:0}


while memory:
Thread ID: 70118283774380
Total: 0.040000

 %self     total     self     wait    child    calls  name
 50.00      0.04     0.02     0.00     0.02      500  Object#fib_while (fib_benchmarks.rb:26}
 25.00      0.01     0.01     0.00     0.00    11000  Fixnum#> (ruby_runtime:0}
 25.00      0.01     0.01     0.00     0.00    10500  Fixnum#+ (ruby_runtime:0}
  0.00      0.00     0.00     0.00     0.00    10500  Fixnum#- (ruby_runtime:0}
  0.00      0.04     0.00     0.00     0.04        1  Integer#times (ruby_runtime:0}
  0.00      0.04     0.00     0.00     0.04        1  Object#profile (fib_benchmarks.rb:48}
  0.00      0.04     0.00     0.00     0.04      500  Proc#call (ruby_runtime:0}


inf memory:
Thread ID: 70118283774380
Total: 63.810000

 %self     total     self     wait    child    calls  name
  3.96      2.53     2.53     0.00     0.00   126500  LazyCons#initialize (./fib_inf_list.rb:18}
  1.13     42.51     0.72     0.00    41.79   220500  Proc#call-1 (ruby_runtime:0}
  0.66      3.16     0.42     0.00     2.74   115500  LazyCons#scanl (./fib_inf_list.rb:37}
  0.53      2.94     0.34     0.00     2.60   126500  Class#new (ruby_runtime:0}
  0.38     37.95     0.24     0.00    37.71   105000  LazyCons#rest-1 (./fib_inf_list.rb:24}
  0.16      0.10     0.10     0.00     0.00   105000  Fixnum#+ (ruby_runtime:0}
  0.13     63.81     0.08     0.00    63.73    10500  LazyCons#take-1 (./fib_inf_list.rb:41}
  0.11      0.07     0.07     0.00     0.00   126500  #allocate (ruby_runtime:0}
  0.08      0.25     0.05     0.00     0.20    11000  Object#fibs (./fib_inf_list.rb:56}
  0.03      0.02     0.02     0.00     0.00    10500  Array#+ (ruby_runtime:0}
  0.03      4.60     0.02     0.00     4.58      500  Proc#call (ruby_runtime:0}
  0.02      4.48     0.01     0.00     4.47    10500  LazyCons#rest (./fib_inf_list.rb:24}
  0.00      4.60     0.00     0.00     4.60        1  Integer#times (ruby_runtime:0}
  0.00      4.58     0.00     0.00     4.58      500  LazyCons#take (./fib_inf_list.rb:41}
  0.00      4.60     0.00     0.00     4.60        1  Object#profile (fib_benchmarks.rb:48}
  0.00      4.58     0.00     0.00     4.58      500  Object#fib_inf_list (./fib_inf_list.rb:52}
  0.00      0.00     0.00     0.00     0.00    10500  Fixnum#- (ruby_runtime:0}
  0.00      0.00     0.00     0.00     0.00    11000  Fixnum#< (ruby_runtime:0}
  0.00      0.00     0.00     0.00     0.00    11000  Fixnum#zero? (ruby_runtime:0}
  0.00      0.00     0.00     0.00     0.00      500  Array#first (ruby_runtime:0}
Advertisements
%d bloggers like this: