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@xxxxxxxxxxxxx> 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

.

Relevant Pages