Ruby Voodoo

The Three Tick Sort

Yesterday I showed a newer programmer some code like scores.sort_by(&:reverse). This provoked a comment about how they where going to look up sort_by() later to figure out what magic is involved here. It made me sad to realize how many cool tricks they weren't going to see in that bit of documentation.

Allow me to enumerate those tricks for you, but first let's flesh out an example. Consider this code:

scores = {
  fifteen:         2,
  five_card_run:   5,
  five_card_flush: 5,
  four_card_run:   4,
  four_card_flush: 4,
  his_nobs:        1,
  pair:            2,
  three_card_run:  3,
}
scores.sort_by(&:reverse).each do |name, score|
  puts "Score #{score} for #{name}."
end
# >> Score 1 for his_nobs.
# >> Score 2 for fifteen.
# >> Score 2 for pair.
# >> Score 3 for three_card_run.
# >> Score 4 for four_card_flush.
# >> Score 4 for four_card_run.
# >> Score 5 for five_card_flush.
# >> Score 5 for five_card_run.

In this case, the magic method call (scores.sort_by(&:reverse)) has reordered a list of Cribbage hands first by point value and then alphabetically ("ASCIIabetically" in truth). How this happens is a pretty interesting journey though.

Let's take it a piece at a time.

First you need to know that Hash#each iterates over pairs. (All other iterators, like sort_by(), use each() under the hood, remember.) A pair is a two element Array containing key then value. If your block takes one argument, you'll get this pair Array. If it takes more, Ruby will extract the values out of the Array due to its "multiple assignment" rules. In other words, you can do this:

hash.each do |key, value|
  # ...
end

or this:

hash.each do |pair|
  # ...
end

This means I could have used sort_by { |key, value| [value, key] }, but I used the Array interface instead: sort_by { |pair| pair.reverse }.

That leads us to the second part of this magic trick: you can sort_by() an Array? Yes, you can.

sort_by() works with any object that defines the spaceship operator (<=>), which Array does:

>> [0] <=> [0]
=> 0
>> [1] <=> [2]
=> -1
>> [2] <=> [1]
=> 1

As you probably work out from the code above, Array objects compare themselves based on their contents. Later elements are used to break ties from earlier comparisons:

>> [0, 1] <=> [0, 2]
=> -1
>> [0, 2] <=> [0, 1]
=> 1

By calling reverse() on the pairs in the sorting Array, I put the score into the primary sorting role and used the hand name as a tie breaker.

That pretty much explains what the block I passed to the iterator did, so there's just one problem left: I didn't actually use a block!

When you have a block of the form method { |object| object.thing_i_care_about } you can rewrite it as method(&:thing_i_care_about). Again we need to break this trick down into pieces to understand it.

First, :thing_i_care_about is a Symbol:

>> :thing_i_care_about
=> :thing_i_care_about
>> :thing_i_care_about.class
=> Symbol

Next, Ruby will try to convert the final argument to a method into a Proc object, if it's proceeded by a &:

>> def m(&block) block end
=> :m
>> m(&Object.new)
TypeError: wrong argument type Object (expected Proc)
    from (irb):4
    from /Users/jeg2/.rubies/ruby-2.1.3/bin/irb:11:in `<main>'

Then you have to know that any object can choose to play ball as a Proc by defining a to_proc() method:

>> o = Object.new
=> #<Object:0x007fc5841fb278>
>> def o.to_proc; proc { puts "Howdy." } end
=> :to_proc
>> m(&o)
=> #<Proc:0x007fc5841e6d28@(irb):8>

Now, you can probably guess that Symbol defines to_proc. Watch what it does:

>> symbol_to_proc = :to_s.to_proc
=> #<Proc:0x007fc5841e2750>
>> symbol_to_proc[42]
=> "42"
>> symbol_to_proc[Object.new]
=> "#<Object:0x007fc5841c1a50>"

See how it just calls the method named after the Symbol? (It's essentially using send() under the hood.)

Combine all of those bits together and you can do some pretty fancy sorting with very little code.