hello! first post to clr. I'm asking about an attempt at a lazy rubysolution to computing fibonacci

Discussion in 'Ruby' started by tphyahoo, Aug 6, 2008.

  1. tphyahoo

    tphyahoo Guest

    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/

    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/

    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/

    # 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...
    tphyahoo, Aug 6, 2008
    #1
    1. Advertising

  2. tphyahoo

    Ryan Davis Guest

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


    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/
    >
    > # 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:

    > # 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.
    Ryan Davis, Aug 6, 2008
    #2
    1. Advertising

  3. Re: hello! first post to clr. I'm asking about an attempt at

    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
    --
    Posted via http://www.ruby-forum.com/.
    Maciej Tomaka, Aug 7, 2008
    #3
  4. Re: hello! first post to clr. I'm asking about an attempt at

    Maciej Tomaka wrote:
    > By the way, you are hunting ants with an rpg:p


    He is hunting ants with a role playing game? ;)
    --
    Posted via http://www.ruby-forum.com/.
    Lloyd Linklater, Aug 7, 2008
    #4
  5. Lloyd Linklater, Aug 7, 2008
    #5
  6. tphyahoo

    Guest

    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 <> 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}
    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)
    yield self
    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
    , Aug 7, 2008
    #6
  7. Re: hello! first post to clr. I'm asking about an attempt at

    Lloyd Linklater 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 ;)
    --
    Posted via http://www.ruby-forum.com/.
    Maciej Tomaka, Aug 8, 2008
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Alex Vinokur
    Replies:
    0
    Views:
    469
    Alex Vinokur
    Oct 29, 2003
  2. Alex Vinokur
    Replies:
    0
    Views:
    435
    Alex Vinokur
    Jul 26, 2004
  3. SenthilVel
    Replies:
    0
    Views:
    421
    SenthilVel
    Sep 7, 2006
  4. Roy
    Replies:
    6
    Views:
    607
    Roedy Green
    Jan 7, 2008
  5. GMI
    Replies:
    3
    Views:
    500
    Tad McClellan
    Jun 19, 2005
Loading...

Share This Page