An Infinite List of Fibonacci Numbers in Ruby

So I was reading through the Haskell Prelude when I stumbled across `scanl' as a kind of abstraction over `foldl'. I stared, and thought, and stared some more, and couldn’t come up with a use for it; a quick Web search revealed exactly one use: Fibonacci numbers.

(In retrospect: duh.)

So here are all the Fibonacci numbers in Haskell:

fibs = 0 : scanl (+) 1 fibs

As you can see this makes use of infinite, recursive lists. So I wrote this in Ruby.

First I needed infinite lists:

class LazyEmpty
  def empty?
    true
  end
end

class LazyCons
  attr_reader :first

  def initialize(first, &rest)
    @first = first
    @rest = rest
    @rest_called = false
  end

  def rest
    if @rest_called
      @rest
    else
      @rest_called = true
      @rest = @rest.call
    end
  end

  def empty?
    false
  end
end

And now that I have such a thing, I need behavior on it. For example, #take will produce the first n elements of such a list:

class LazyEmpty
  def take(n)
    LazyEmpty.new
  end
end
class LazyCons
  def take(n)
    if n < 0
      self
    elsif n.zero?
      [self.first]
    else
      self.rest.take(n-1) + [self.first]
    end
  end
end

So now I can get at the elements:

irb(main):001:0> l = LazyCons.new(1) { LazyCons.new(2) { LazyCons.new(3) { LazyCons.new(4) { LazyEmpty.new }}}}
=> #<LazyCons:0x7f656ee21208 @rest_called=false, @rest=#<Proc:0x00007f656ee212a8@(irb):2>, @first=1>
irb(main):002:0> l.take(2)
=> [3, 2, 1]

To get the most fun definition for the list of Fibonacci numbers I need #scanl:

class LazyEmpty
  def scanl(q, &f)
    LazyCons.new(q) { LazyEmpty.new }
  end
end

class LazyCons
  def scanl(q, &f)
    LazyCons.new(q) { self.rest.scanl(f.call(q, self.first), &f) }
  end
end

So now I have all the parts needed:

def fibs
  LazyCons.new(0) { fibs.scanl(1) {|x,y| x + y} }
end

See?

irb(main):008:0> fibs.take(10)
=> [55, 34, 21, 13, 8, 5, 3, 2, 1, 1, 0]

That is to say, the nth Fibonacci number is the first element from take(n).

def fib(n)
  fibs.take(n).first
end

At this point I wondered how it performed, especially against the naïve implementation. So I used Benchmark.rb and ruby-prof to compare #fib_naive, #fib_tail (the tail-call rewrite of the naïve implementation), #fib_while (the while loop rewrite of the tail-call rewrite), and #fib_inf_list (as defined above) … and the infinite list was not in last place!

       user       system      total        real
naive 12.020000   2.140000  14.160000 ( 14.174045)
tail   0.000000   0.000000   0.000000 (  0.010399)
while  0.020000   0.000000   0.020000 (  0.008730)
inf    3.360000   0.150000   3.510000 (  3.513216)

naive memory:
Thread ID: 70118283774380
Total: 970.630000

 %self     total     self     wait    child    calls  name
  5.11    970.63    49.61     0.00   921.02 17710000  Object#fib_naive-1 (fib_benchmarks.rb:6}
  1.01      9.79     9.79     0.00     0.00 17710000  Fixnum#- (ruby_runtime:0}
  0.94      9.16     9.16     0.00     0.00 17710500  Fixnum#< (ruby_runtime:0}
  0.53      5.17     5.17     0.00     0.00  8855000  Fixnum#+ (ruby_runtime:0}
  0.00     73.73     0.00     0.00    73.73        1  Integer#times (ruby_runtime:0}
  0.00     73.73     0.00     0.00    73.73      500  Proc#call (ruby_runtime:0}

  0.00     73.73     0.00     0.00    73.73      500  Object#fib_naive (fib_benchmarks.rb:6}
  0.00     73.73     0.00     0.00    73.73        1  Object#profile (fib_benchmarks.rb:48}

tail memory:
Thread ID: 70118283774380
Total: 0.630000

 %self     total     self     wait    child    calls  name
  6.35      0.63     0.04     0.00     0.59    10500  Object#fib_tail_aux-1 (fib_benchmarks.rb:18}
  1.59      0.01     0.01     0.00     0.00    10500  Fixnum#+ (ruby_runtime:0}
  0.00      0.00     0.00     0.00     0.00    10500  Fixnum#- (ruby_runtime:0}
  0.00      0.05     0.00     0.00     0.05      500  Object#fib_tail_aux (fib_benchmarks.rb:18}
  0.00      0.05     0.00     0.00     0.05      500  Object#fib_tail (fib_benchmarks.rb:14}
  0.00      0.05     0.00     0.00     0.05        1  Integer#times (ruby_runtime:0}
  0.00      0.00     0.00     0.00     0.00    11000  Fixnum#zero? (ruby_runtime:0}
  0.00      0.05     0.00     0.00     0.05        1  Object#profile (fib_benchmarks.rb:48}
  0.00      0.05     0.00     0.00     0.05      500  Proc#call (ruby_runtime:0}

while memory:
Thread ID: 70118283774380
Total: 0.040000

 %self     total     self     wait    child    calls  name
 50.00      0.04     0.02     0.00     0.02      500  Object#fib_while (fib_benchmarks.rb:26}
 25.00      0.01     0.01     0.00     0.00    11000  Fixnum#> (ruby_runtime:0}
 25.00      0.01     0.01     0.00     0.00    10500  Fixnum#+ (ruby_runtime:0}
  0.00      0.00     0.00     0.00     0.00    10500  Fixnum#- (ruby_runtime:0}
  0.00      0.04     0.00     0.00     0.04        1  Integer#times (ruby_runtime:0}
  0.00      0.04     0.00     0.00     0.04        1  Object#profile (fib_benchmarks.rb:48}
  0.00      0.04     0.00     0.00     0.04      500  Proc#call (ruby_runtime:0}

inf memory:
Thread ID: 70118283774380
Total: 63.810000

 %self     total     self     wait    child    calls  name
  3.96      2.53     2.53     0.00     0.00   126500  LazyCons#initialize (./fib_inf_list.rb:18}
  1.13     42.51     0.72     0.00    41.79   220500  Proc#call-1 (ruby_runtime:0}
  0.66      3.16     0.42     0.00     2.74   115500  LazyCons#scanl (./fib_inf_list.rb:37}
  0.53      2.94     0.34     0.00     2.60   126500  Class#new (ruby_runtime:0}
  0.38     37.95     0.24     0.00    37.71   105000  LazyCons#rest-1 (./fib_inf_list.rb:24}
  0.16      0.10     0.10     0.00     0.00   105000  Fixnum#+ (ruby_runtime:0}
  0.13     63.81     0.08     0.00    63.73    10500  LazyCons#take-1 (./fib_inf_list.rb:41}
  0.11      0.07     0.07     0.00     0.00   126500  #allocate (ruby_runtime:0}
  0.08      0.25     0.05     0.00     0.20    11000  Object#fibs (./fib_inf_list.rb:56}
  0.03      0.02     0.02     0.00     0.00    10500  Array#+ (ruby_runtime:0}
  0.03      4.60     0.02     0.00     4.58      500  Proc#call (ruby_runtime:0}
  0.02      4.48     0.01     0.00     4.47    10500  LazyCons#rest (./fib_inf_list.rb:24}
  0.00      4.60     0.00     0.00     4.60        1  Integer#times (ruby_runtime:0}
  0.00      4.58     0.00     0.00     4.58      500  LazyCons#take (./fib_inf_list.rb:41}
  0.00      4.60     0.00     0.00     4.60        1  Object#profile (fib_benchmarks.rb:48}
  0.00      4.58     0.00     0.00     4.58      500  Object#fib_inf_list (./fib_inf_list.rb:52}
  0.00      0.00     0.00     0.00     0.00    10500  Fixnum#- (ruby_runtime:0}
  0.00      0.00     0.00     0.00     0.00    11000  Fixnum#< (ruby_runtime:0}
  0.00      0.00     0.00     0.00     0.00    11000  Fixnum#zero? (ruby_runtime:0}
  0.00      0.00     0.00     0.00     0.00      500  Array#first (ruby_runtime:0}

Powerset in Ruby Using the List Monad

While trying to think of good, quick interview questions I stumbled across power set (thanks to Mike DiStaula for suggesting it). After 10 minutes of hacking in Ruby I discovered that it’s not a reasonable replacement for our current starter question (it takes too long), but it’s also a fun problem to solve.

Then I wandered across this definition of power set in Haskell:

powerset = filterM (const [True, False])

Well, that was easy. So I set out to write that in Ruby. That is, I wanted to write this:

class Array
  def powerset
    self.filterM {|x| [true, false]}
  end
end

First thing I need is a list monad:

class Array
  def self.unit(x)
    [x]
  end

  def bind(&f)
    self.inject([]) do |acc, e|
      acc + f.call(e)
    end
  end
end

I quickly hit my weekly reminder that Ruby does not have Array#rest, so I added that:

class Array
  def rest
    r = self[1..-1]
    r.nil? ? [] : r
  end
end

Whew; now things are easier. Next I needed filterM, so I added it to Enumerable as a faithful copy from Haskell (expanding the do notation into the >>= notation):

module Enumerable
  def filterM(&p)
    return self.class.unit([]) if self.empty?
    p.call(self.first).bind do |flg|
      self.rest.filterM(&p).bind do |ys|
        self.class.unit(flg ? ([self.first] + ys) : ys)
      end
    end
  end
end

Now my original Array#powerset method works:

irb(main):013:0> [1,2,3].powerset
=> [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

I expect you to write that quickly in your next interview.

Correctly Handle OpenID Updates

OpenID is pretty well established as a login infrastructure, but a topic often ignored is correctly letting the user change his saved OpenID. Don’t just save the text they enter! Verify that they’ve entered their valid OpenID.

The user model needs to pass this test:

should_have_db_column :new_openid_identity, :type => 'string'

The view on /account/edit needs to pass this test:

context "logged in" do
  setup { session[:user_id] = Factory(:user).id }

  context "GET to edit" do
    setup { get :edit }

    should "have a form for their OpenID info" do
      assert_select 'form[action=?][method=post]', openid_path do
        assert_select 'input[type=hidden][name=_method][value=put]'
        assert_select 'input[type=text][name=?]',
                      'user[new_openid_identity]'
        assert_select 'input[type=submit]'
      end
    end
  end
end

And, most importantly, the OpenidsController needs to pass the test suite in gist 23084.

(All these tests assume FactoryGirl and Shoulda; re-write in RSpec or PyUnit or whatever as you see fit.)

Save Those Receipts!

Over the weekend I was on a team of (potential) winners participating in the 2008 Rails Rumble. The application idea was something that I had prototyped for myself years ago and quickly lost, and it solves the problem I had at the time:

I was living near Fenway, and I suffered from too many choices of where to purchase milk (and other groceries). The best solution, to me, was to track the price of milk at various shops so I could have an accurate measurement of which was cheapest, or if there were any correlations I could use to predict the price.

That’s it.

So Chad, Joe, Micah, and myself met the day before it started and mapped out a gameplan for Where’s The Milk At. We watched Blur’s “Coffee & TV” for visual inspiration, drew mocks on paper, and discussed just how awesome we’re gonna rock.

Chad, Micah, and myself set to work at 8PM EDT on Friday (midnight GMT), lasting until 2:30AM. Fueled by pizza, we knocked out most of the server setup, sign up and sign up (both password and OpenID), page layout and design, and the logo.

The next day Joe joined in to hack from 9AM to 9PM (Chad stayed until midnight), fixing some bugs and propelling forward with some crazy JavaScript. More pizza was ordered, and Joe’s girlfriend stopped by with some delicious, large cookies.

I felt unrested and failed to pull my own weight on Saturday, but on Sunday we all worked full-steam toward the 8PM EDT deadline. We found browser incompatibilities with two hours to go, and two bugs in our code with an hour to go; we were down to the wire, but we got everything in with 30 minutes to spare. (Joe used those 30 minutes to improve the JavaScript.)

All of this was caught on video.

Inspired by this weekend of hacking for 32.5 hours, I’ve started work on another idea I suggested during the brainstorming (word blogging), with the intent of doing a 12-hour code sprint on Saturday with anyone who is willing to join. Find me on IRC to join in.

Uniquify an array of hashes in Ruby

Array#uniq is a handy Ruby method that produces an array of distinct elements. So, for example, [1,2,3,3,3].uniq produces [1,2,3].

However, this fails on an array of hashes. For example, [{}, {}].uniq actually produces [{},{}]. That’s not what I wanted, recently.

It turns out that #uniq uses the methods #hash and #eql? to determine uniqueness, and Hash#hash produces the object_id, and {}.eql?({}) produces false.

To solve this, I redefined #hash and #eql? for the hash instances before I put them in the array:

h = {}
class <<h
  def hash
    values.inject(0) { |acc,value| acc + value.hash }
  end

  def eql?(a_hash)
    self == a_hash
  end
end

It should be noted that calling #dup on this hash will then screw things up, but that’s common to all Ruby eigenclass fun.

However, you could just use a proper class instead of a hash, ’cause this isn’t Perl.

Spider bugfix

There were two issues with version 0.4.0 of Spider, both caught by Henri Cook. These are now fixed in 0.4.1:

• As documented, you use IncludedInMemcached like this: require 'spider/included_in_memcached' .
• Sometimes HTTP redirects assume a base URL; this is now handled.

Spider with memcached

The problem with Spider has been that it can use all your memory. The reason is that the Web is a graph, and to avoid cycles Spider stores each URL it encounters. Since the Web is a really, really, really gigantic graph, you eventually run out of memory.

Now you can use memcached to use not only all the memory on one computer, but all the memory on many computers!

require 'spider'
require 'spider/included_in_memcached'
SERVERS = ['10.0.10.2:11211','10.0.10.3:11211','10.0.10.4:11211']
Spider.start_at('http://mike-burns.com/') do |s|
  s.check_already_seen_with IncludedInMemcached.new(SERVERS)
end

Also new in this version is a tutorial on the main Spider Web site. Yeah!

Proxied Spider

Aha: if you need to proxy your Spider calls, look no further than the HTTP Configuration gem.

I didn’t write this, and have yet to use it, but I think it goes like this:

http_conf = Net::HTTP::Configuration.new(:proxy_host => 'localhost', :proxy_port => 8881)
http_conf.apply do
  Spider.start_at('http://example.com/')
end

So next up will be a tutorial with stuff like this and other cool stuff, plus a way to use memcached with Spider.

Spider: API changes, setup and teardown, HTTP headers

The newest version of Spider, 0.3.0, is hitting your gem tree Real Soon Now. This release features:

Set the headers to a HTTP request.

This can be used to set the cookies, user agent, and many other fine things.

setup and teardown handlers.

Seems like a good place to set the headers if the headers are conditional on the URL.

Say :every, not :any.

Makes more sense this way, I claim.

All the handlers take the same three arguments.

The URL, the response, and—new—the calling URL.

Next on my list: proxies, a better way to store whether an URL has been seen, then a tutorial.

Get it the usual way: gem install spider

Spider bug fix release

John Nagro immediately reported errors with the Spider Ruby gem, so I’ve fixed them in 0.2.1. You should upgrade, especially if you want support for:

• URLs without any path component (e.g. http://example.com?s=1).
• HTTP redirects.
• HTTPS.

John also had some good ideas, so here is what is in the works:

• The ability to construct a complete graph of every node found.
• Defeat cycles using memcached instead of memory (closely related to the above bullet).
• A Net::HTTP abstraction that makes it easier to e.g. use a proxy or replace HTTP.