From: brabuhr@...
Date: 2008-08-08T06:49:12+09:00
Subject: Re: hello! first post to clr. I'm asking about an attempt at a lazy ruby solution to computing fibonacci numbers for a project euler problem. seems to be a bug in lazy ruby...

On Wed, Aug 6, 2008 at 3:51 PM, Ryan Davis <ryand-ruby@zenspider.com> wrote:
> On Aug 6, 2008, at 08:40 , tphyahoo wrote:
>
>> t = ( putStrLn . show . sum . takeWhile (<=4000000) . filter even )
>> fibs2
>> fibs2 = 1 : 2 : zipWith (+) fibs2 (tail fibs2)
>
> Gives me hives personally... I've never been able to handle the syntax of
> haskell.
>
>> but it relies on laziness and who knows what other magic.
>
> The laziness I'm fine with... the other magic? not so much.
>
>> I decided to see if I could find a ruby solution that was more
>> haskellish. It turns I can... almost.
>
> Here is my ruby-idiomatic solution to the problem:
>
>> # Solve Project Euler problem 2:
>> #   sum fibonacci numbers <= 4_000_000, which are even.
>>
>> $fib = {} # simple memoization
>> def fib x
>>  $fib[x] ||= x < 2 ? 1 : fib(x-2) + fib(x-1)
>> end
>>
>> # fib 33 > 4m
>> fibs = (1..32).map { |n| fib n }.reject { |n| n % 2 == 1 }
>>
>> sum = 0
>> fibs.each do |n|
>>  sum += n
>> end
>>
>> p sum
>> # => 4613732
>
> because of the memoization, it runs incredibly fast. If I wasn't allowed to
> predetermine the upper bound of the calculation, I'd wrap that up in a
> simple loop with a conditional... Nothing fancy.

Personally, I like a Ruby memoizing solution, but seeing some other
lazy Ruby projects in a quick Google search, I whipped this up:

require 'lazy_stream'

even = lambda{|int| int[0] == 0}
under_4_million = lambda{|int| int <= 4_000_000 }

fibonacci = lambda{|array, index|
  index < 2 ? 1 : array[index - 2] + array[index - 1]
}

# create a "lazy stream" that generates the fibonacci sequence
fibs = LazyStream.new(fibonacci)

# create a filtered lazy stream of even fibonacci numbers
even_fibs = LazyStream.filter(fibs, even)

# sum the even fibonacci numbers that are less than 4,000,000
sum = 0
even_fibs.each_while(under_4_million){|f| sum += f}
puts sum
# => 4613732

And the evil class that makes it "work":

# A *very* simple lazy generator based on Array
class LazyStream < Array

  # When creating a LazyStream, supply a generator lambda.
  # The generator should take as parameters the stream and the index.
  def initialize generator
    @generator = generator
  end

  # Override the basic array [] to generate as necessary.
  def [](index)
    if index.is_a? Range
      index.map{|i| self[i]}
    else
      (self.fetch(index) rescue nil) ||
        self[index] = @generator.call(self, index)
    end
  end

  # Loop through the stream until the value evaluates the block to false.
  def each_while filter
    i = 0
    loop do
      break unless filter.call(self[i])
      yield self[i]
      i += 1
    end
  end

  # Create a new stream that applies a filter to an existing stream.
  def self.filter other_stream, filter
    new_stream = new lambda{|s, index|
      v = nil; @other_index ||= 0

      index.times{|n| new_stream[n]} if index > new_stream.size

      loop{
        v = other_stream[@other_index]
        @other_index += 1
        break if filter.call(v)
      }
      v
    }
  end

private

  # Move the basic array []= to private so people don't muck around with it :-)
  def []=(index, value)
    super(index, value)
  end
end