Impementation of the Ruby <=> Combinator

Question

Not infrequently, one wants to implement the <=> (comparison, or "spaceship") operator on a product data type, i.e., a class with multiple fields (all of which (we hope!) already have <=> implemented), comparing the fields in a certain order.

def <=>(o)
    f1 < o.f1 && (return -1)
    f1 > o.f1 && (return  1)
    f2 < o.f2 && (return -1)
    f2 > o.f2 && (return  1)
    return 0
end

This is both tedious and error-prone, especially with a lot of fields. It's error-prone enough that I frequently feel I should unit test that function, which just adds to the tediousness and verbosity.

Haskell offers a particularly nice way of doing this:

import Data.Monoid (mappend)
import Data.Ord (comparing)

-- From the standard library:
-- data Ordering = LT | EQ | GT

data D = D { f3 :: Int, f2 :: Double, f1 :: Char } deriving Show

compareD :: D -> D -> Ordering
compareD = foldl1 mappend [comparing f1, comparing f2, comparing f3]

(For those not familiar with fold, the above expands to

comparing f1 `mappend` comparing f2 `mappend` comparing f3

which produces a function that can be applied to two Ds, to produce an Ordering.)

The defintion of compareD is so simple that it's obviously correct, and I wouldn't feel the need to unit test it even without static type checking.

Actually, the question may be even slightly more interesting than this, since I may not want to use just the standard <=> operator, but sort in different ways at different times, e.g.:

sortByOrderings :: [a -> a -> Ordering] -> [a] -> [a]
sortByOrderings = sortBy . foldl1 mappend

sortByF3F1 = sortByOrderings [comparing f3, comparing f1]
sortByF2F3 = sortByOrderings [comparing f2, comparing f3]

So, the questions:

1. What's the typical way of implementing this sort of thing in Ruby?
2. What's the nicest way of doing it using just what's defined in the standard libraries?
3. How close can one get to the Haskell code above, and how reliable is it, in comparison? If necessary, how can one ensure that the fields have a properly implemented <=> or < and > operators?

Incidently, while this is a Ruby question, I'm happy to consider discussion of the Haskell techniques on-topic if the elders of this site so agree. Please feel free to comment on whether that's appropriate or not and, if it is, tag this post 'haskell' as well.

Butts

Answer 1

Here's a riff on your idea. It doesn't define any extra constants, allows you to use any combination of instance variables and methods to compare two objects, has early exit on not-equal, and includes all the methods defined by Comparable.

class Object
    def self.compare_by(*symbols)
        include Comparable
        dispatchers = symbols.map do |symbol|
          if symbol.to_s =~ /^@/
            lambda { |o| o.instance_variable_get(symbol) }
          else
            lambda { |o| o.__send__(symbol) }
          end
        end
        define_method('<=>') do |other|
          dispatchers.inject(0) do |_,dispatcher|
            comp = dispatcher[self] <=> dispatcher[other]
            break comp if comp != 0
            comp
          end
        end
    end
end

class T
    def initialize(name,f1,f2,f3)
      @name,@f1, @f2, @f3 = name,f1, f2, f3;
    end

    def f1
      puts "checking #@name's f1"
      @f1
    end
    def f3
      puts "checking #@name's f3"
      @f3
    end

    compare_by :f1, :@f2, :f3
end

w = T.new('x',1,1,2)
x = T.new('x',1,2,3)
y = T.new('y',2,3,4)
z = T.new('z',2,3,5)

p w < x   #=> checking x's f1
          #   checking x's f1
          #   true
p x == y  #=> checking x's f1
          #   checking y's f1
          #   false
p y <= z  #=> checking y's f1
          #   checking z's f1
          #   checking y's f3
          #   checking z's f3
          #   true

If you wanted, you could insert some extra error checking in there to make sure that the values used to compare actually respond to <=> (using respond_to? '<=>'), and try to give clearer error messages in the case wwhere they don't.

Logroll

Great stuff. It doesn't get me the same easy sortBy thing that Haskell does, but it sure does a great job of dealing with default comparisons! – Butts

Bear in mind that you can use Enumerable#sort in pretty much the same way as Haskell's List.sortBy (just without the currying, sorry). And Enumerable#sort_by lets you define the sorting key at sort time. – Logroll

Answer 2

Here's what I do to make custom sorting rules more manageable: on all my classes I ever need to sort, I define "to_sort" methods that return arrays, and then override <=> to use to_sort:

class Whatever
  def to_sort
    [@mainkey,@subkey,@subsubkey]
  end

  def <=>(o)
    self.to_sort <=> o.to_sort
  end
end

Thus sorting any array of Whatevers (including heterogeneous arrays of Whatevers and Whateverothers and Whathaveyours, all of which implement type-specific to_sort functions and this same <=> override) just devolves internally to sorting an array of arrays.

Hapten

Note, this will blow up if any of your instance variables are nil. – Squib

Answer 3

I took a similar approach as rampion, but wanted to handle the case where attributes could be nil.

module ComparableBy
  def comparable_by(*attributes)
    include Comparable

    define_method(:<=>) do |other|
      return if other.nil?
      attributes.each do |attribute|
        left  = self.__send__(attribute)
        right = other.__send__(attribute)
        return -1 if left.nil?
        return 1 if right.nil?
        comparison = left <=> right
        return comparison unless comparison == 0
      end
      return 0
    end
  end
end

Example Usage:

SomeObject = Struct.new(:a, :b, :c) do
  extend ComparableBy
  comparable_by :a, :b, :c
end

Squib

Answer 4

Well, here's a quick hack at an extension to Object to make this happen in what seems to be a reasonably nice way.

class Object

    def self.spaceship_uses(*methods)
        self.const_set(:SPACESHIP_USES, methods)
    end

    def <=>(o)
        raise(NoMethodError, "undefined method `<=>' for #{self.inspect}") \
            unless self.class.const_defined?(:SPACESHIP_USES)
        self.class.const_get(:SPACESHIP_USES).each { |sym|
            self.send(sym) < o.send(sym) && (return -1)
            self.send(sym) > o.send(sym) && (return  1)
        }
        return 0
    end

end

class T

    def initialize(f1, f2) @f1, @f2 = f1, f2; end

    attr_reader    :f1, :f2
    spaceship_uses :f1, :f2

end

This of course doesn't deal with any typing issues, to make sure that < and > are properly implemented for the objects returned by the methods in SPACESHIP_USES. But then gain, being Ruby, this is probably fine, isn't it?

Short comments can comment on this, but I'd be interested in seeing detailed discussion and extensions in other answers.

Butts

This version means that all objects will respond_to?(:<=>), but most will raise a NoMethodError. That's not a good idea. You might try moving the definition of :<=> into the :spaceship_uses call, which would fix the problem. Just use define_method(:<=>) do ... end – Quadrat

also, don't forget to include Comparagble, so your other comparison operators are defined for you. – Logroll

Here's a modification that includes my and Gaius's changes: gist.github.com/114798 – Logroll

Hey, rampion, that's really awesome, rubyish code. Bravo! ( Or Brava! if you're a gal, but there is a mustache on your profile pic after all :) ) – Quadrat