# Hello! first post to clr. I'm asking about an attempt at a lazy ruby solution to computing fibonacc

**URL:** <https://www.ruby-forum.com/t/hello-first-post-to-clr-im-asking-about-an-attempt-at-a-lazy-ruby-solution-to-computing-fibonacc/145174>\
**Category:** Ruby\
**Created:** [August 6, 2008, 5:42pm UTC](https://www.ruby-forum.com/t/hello-first-post-to-clr-im-asking-about-an-attempt-at-a-lazy-ruby-solution-to-computing-fibonacc/145174 "2008-08-06T17:42:32Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![tphyahoo](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/91b2a8/32.png) [@tphyahoo](https://www.ruby-forum.com/u/tphyahoo)\
**Post date:** [August 6, 2008, 5:42pm UTC](https://www.ruby-forum.com/t/hello-first-post-to-clr-im-asking-about-an-attempt-at-a-lazy-ruby-solution-to-computing-fibonacc/145174/1 "2008-08-06T17:42:32Z")

</div>

Hi, first post to clr here.

I have a guess a haskell bias as that’s the last language I learned,  
and now I’m learning ruby.

I was trying to solve project euler problem 2 as an exercise. This is,  
sum all the even fibonacci numbers less than 4 million.

There is a solution that works at

[http://www.absorbeo.net/2008/01/10/project-euler-problem-2/](http://www.absorbeo.net/2008/01/10/project-euler-problem-2/)

however I didn’t quite like it because the test for evenness is in the  
fold (haskell speak for inject).

puts a.inject(0) {|s,v|  
if v \> 1\_000\_000 then  
break s  
elsif v % 2 == 0  
s+v  
else  
s  
end  
}

the haskell solution reads nicer to me

t = ( putStrLn . show . sum . takeWhile (\<=4000000) . filter even )  
fibs2  
fibs2 = 1 : 2 : zipWith (+) fibs2 (tail fibs2)

but it relies on laziness and who knows what other magic.

I decided to see if I could find a ruby solution that was more  
haskellish. It turns I can… almost.

There is a ruby library for laziness

# [http://lazylist.rubyforge.org/](http://lazylist.rubyforge.org/)

and it would seem to do what I want. But it hangs for some reason.

I have poor sense of ruby culture. Should I report this as a bug? Is  
it even a bug? Do people ever use laziness, or is this crazy  
experimentation?

Thanks for help and advice!

Code below:

thartman@thartman-laptop:~/thomashartman-learning/ruby/katas/euler\>cat  
2.rb  
require ‘rubygems’  
require ‘lazylist’ # [http://lazylist.rubyforge.org/](http://lazylist.rubyforge.org/)

# Solve Project Euler problem 2: sum fibonacci numbers \<= 4\_000\_000,

which are even.  
fibs = ( LazyList.tabulate(0) { |x| x \< 2 ? 1 : fibs[x-2] +  
fibs[x-1] } )

fibsUnder4M = ( fibs.partition{ |x| x \<= 4\_000\_000 })[0]  
evenFibsUnder4M = fibsUnder4M.select{ |x| x %2 == 0}

# problem seems to be with partition

# evenFibsLessThanFourMil = ( evenFibs.partition{ |x| x \<= 4\_000\_000 })

[0]

# works

# puts evenFibsLessThanFourMil.take(1)

# hangs

puts evenFibsUnder4M.take(10) # this is ok  
puts evenFibsUnder4M.take(11) # this hangs, laptop gets hot, fan turns  
on…

# exit

# this would be the answer to the euler problem, if only there wasn’t

the bug…  
result = evenFibsLessThanFourMil.inject(0){ | accum,val | accum + val}

main = puts result  
thartman@thartman-laptop:~/thomashartman-learning/ruby/katas/  
euler\>ruby 2.rb  
2  
8  
34  
144  
610  
2584  
10946  
46368  
196418  
832040  
… hung…

---

<div class="post-metadata">

**Author:** ![tphyahoo](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/91b2a8/32.png) [@tphyahoo](https://www.ruby-forum.com/u/tphyahoo)\
**Post date:** [August 6, 2008, 9:53pm UTC](https://www.ruby-forum.com/t/hello-first-post-to-clr-im-asking-about-an-attempt-at-a-lazy-ruby-solution-to-computing-fibonacc/145174/2 "2008-08-06T21:53:51Z")

</div>

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.

Ignoring my haskell bias for a bit… I’d recommend doing this, with  
any pairing of languages. Find the idiomatic response appropriate for  
the target language and you’ll have a better time.

> There is a ruby library for laziness
> 
> # [http://lazylist.rubyforge.org/](http://lazylist.rubyforge.org/)

I’ve not used this personally, I suspect using it is the problem.

> and it would seem to do what I want. But it hangs for some reason.
> 
> I have poor sense of ruby culture. Should I report this as a bug? Is  
> it even a bug? Do people ever use laziness, or is this crazy  
> experimentation?

Assuming it is a bug, yes, report it. Again, not having used the  
library, I can’t really weigh in whether this behavior is a bug or not.

> require ‘rubygems’  
> require ‘lazylist’ # [http://lazylist.rubyforge.org/](http://lazylist.rubyforge.org/)
> 
> # Solve Project Euler problem 2: sum fibonacci numbers \<= 4\_000\_000,
> 
> which are even.  
> fibs = ( LazyList.tabulate(0) { |x| x \< 2 ? 1 : fibs[x-2] +  
> fibs[x-1] } )

so, according to the doco, tabulate is a generator function that  
starts at 0 and yields the block on each successive succ.

(stop with all the parens)

> fibsUnder4M = ( fibs.partition{ |x| x \<= 4\_000\_000 })[0]

partition is customized to return two lazy lists, so this _should_ be  
fine.

> evenFibsUnder4M = fibsUnder4M.select{ |x| x %2 == 0}

likewise, select is customized to return a lazy list. again, fine.

> # hangs
> 
> puts evenFibsUnder4M.take(10) # this is ok  
> puts evenFibsUnder4M.take(11) # this hangs, laptop gets hot, fan turns  
> on…

presumably the take actually executes and generates elements from the  
lazy list, unwinding back through the select, the partition, and  
finally the tabulate block. This all looks kosher to me on the surface  
(albeit a bit more complicated than necessary because you’re trying to  
match haskell.

So, I would think that you’ve discovered a bug in the LazyList impl,  
as your logic seems sound.

Here is my ruby-idiomatic solution to the problem:

> 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.

---

<div class="post-metadata">

**Author:** ![tphyahoo](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/91b2a8/32.png) [@tphyahoo](https://www.ruby-forum.com/u/tphyahoo)\
**Post date:** [August 7, 2008, 6:11pm UTC](https://www.ruby-forum.com/t/hello-first-post-to-clr-im-asking-about-an-attempt-at-a-lazy-ruby-solution-to-computing-fibonacc/145174/3 "2008-08-07T18:11:16Z")

</div>

It is implementation failure, you are right.  
LazyList::Enumerable has buggy select which works as follows:

So it search first true occurence and returns new object.

list = LazyList.tabulate(0) { |x| x }  
=\> […]  
less\_than\_three = list.select { |x| x \< 3 }  
lest\_than\_three.take(0);lest\_than\_three.take(1);lest\_than\_three.take(2)  
less\_than\_three.tail  
=\> [1, 2,…]  
less\_than\_three.tail.tail  
=\> [2,…]  
less\_than\_three.tail.tail.tail

# Hangs

So this should return lazy tail (which is empty, infinite loop occurs).

By the way, you are hunting ants with an rpg:P

Best Regards

Maciej

---

<div class="post-metadata">

**Author:** ![tphyahoo](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/91b2a8/32.png) [@tphyahoo](https://www.ruby-forum.com/u/tphyahoo)\
**Post date:** [August 7, 2008, 8:12pm UTC](https://www.ruby-forum.com/t/hello-first-post-to-clr-im-asking-about-an-attempt-at-a-lazy-ruby-solution-to-computing-fibonacc/145174/4 "2008-08-07T20:12:18Z")

</div>

Maciej Tomaka wrote:

> By the way, you are hunting ants with an rpg:P

He is hunting ants with a role playing game? 😉

---

<div class="post-metadata">

**Author:** ![tphyahoo](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/91b2a8/32.png) [@tphyahoo](https://www.ruby-forum.com/u/tphyahoo)\
**Post date:** [August 7, 2008, 8:17pm UTC](https://www.ruby-forum.com/t/hello-first-post-to-clr-im-asking-about-an-attempt-at-a-lazy-ruby-solution-to-computing-fibonacc/145174/5 "2008-08-07T20:17:14Z")

</div>

There is an archive kept of threads and you can find some of this  
discussed already by searching through it. As this is your first, post,  
allow me to give it to as a freebie.

[http://www.ruby-forum.com/forum/4?filter=fibonacci](http://www.ruby-forum.com/forum/4?filter=fibonacci)

---

<div class="post-metadata">

**Author:** ![tphyahoo](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/91b2a8/32.png) [@tphyahoo](https://www.ruby-forum.com/u/tphyahoo)\
**Post date:** [August 8, 2008, 10:17pm UTC](https://www.ruby-forum.com/t/hello-first-post-to-clr-im-asking-about-an-attempt-at-a-lazy-ruby-solution-to-computing-fibonacc/145174/6 "2008-08-08T22:17:40Z")

</div>

Lloyd L. wrote:

> Maciej Tomaka wrote:
> 
> > By the way, you are hunting ants with an rpg:P
> 
> He is hunting ants with a role playing game? 😉

🙂 Have you ever seen Duke Nukem? RPG was a rocket launcher 😉

---

<div class="post-metadata">

**Author:** ![tphyahoo](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/91b2a8/32.png) [@tphyahoo](https://www.ruby-forum.com/u/tphyahoo)\
**Post date:** [August 7, 2008, 11:51pm UTC](https://www.ruby-forum.com/t/hello-first-post-to-clr-im-asking-about-an-attempt-at-a-lazy-ruby-solution-to-computing-fibonacc/145174/7 "2008-08-07T23:51:47Z")

</div>

On Wed, Aug 6, 2008 at 3:51 PM, Ryan D. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
wrote:

> > $fib = {} # simple memoization  
> > 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   
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