memoized_fib.rb

# Ruby Implementation of lazy array for memoized fib
# Inspired by Pat Shaughnessy's talk at http://bostonrb.org/presentations/month/March-2013

# Define a LazyArray class that caches results
# The cache is valid as long as we use it functionally meaning that 
# the fn has no side effects and always returns the same output for the same input
class LazyArray
  def initialize(fn)
    @fn = fn
    @cache = {}
  end

  def [](index)
    @cache[index] ||= @fn.call(self, index)
  end  
end

# Fibonacci numbers. This is what looks just like the
# Haskell Version:
#   memoized_fib = (map fib [0 ..] !!)
#      where fib 0 = 0
#            fib 1 = 1
#            fib n = memoized_fib (n-2)
#                  + memoized_fib (n-1)
memoized_fib = LazyArray.new ->(lazy_array, i) {
  case i
  when 0
    1
  when 1
    1
  else
    lazy_array[i-1] + lazy_array[i-2]
  end
}

# This goes really fast :)
(0..Float::INFINITY).lazy.each {|i| puts "fib(#{i})= #{memoized_fib[i]}" }