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.

Answer 1

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.

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.

Answer 3

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.

Answer 4

I really like glenn mcdonald's answer because it is intuitive and elegantly simple!