Pattern matching and dynamic dispatch

In functional programming, pattern matching is preferred to if expressions. The following example is from The Fun of Programming:

data Colour = Blue | Red
data (Ord a) => Tree a = Null | Fork Colour a (Tree a) (Tree a)

isEmpty Null = True
isEmpty (Fork col x a b) = False

minElem (Fork col x a b) = x

deleteMin (Fork col x a b) = merge a b

insert x a = merge (Fork Blue x Null Null) a

merge a Null = a
merge Null b = b
merge a b
    | minElem a <= minElem b = join a b
    | otherwise = join b a

join (Fork Blue x a b) c = Fork Red x (merge a c) b
join (Fork Red x a b) c = Fork Blue x a (merge b c)

How about object-oriented programming? Dynamic dispatch is preferred to if expressions. The above example can be written in Ruby as follows:

class Tree
  def insert(value)
    BlueFork.new(value, Null, Null).merge(self)
  end

  def merge(other)
    other._merge(self)
  end
end

Null = Tree.new
def Null.empty?
  true
end
def Null.merge(other)
  other
end
def Null._merge(other)
  other
end

class Fork < Tree
  attr_reader :value, :left, :right

  def initialize(value, left, right)
    @value, @left, @right = value, left, right
  end

  def empty?
    false
  end

  def min_elem
    value
  end

  def delete_min
    merge(left, right)
  end

  def _merge(other)
    if min_elem <= other.min_elem 
      self.join(other)
    else
      other.join(self)
    end
  end
end

class BlueFork < Fork
  def join(other)
    RedFork.new(value, left.merge(other), right)
  end
end

class RedFork < Fork
  def join(other)
    BlueFork.new(value, left, right.merge(other))
  end
end

This Ruby code is slightly more verbose than Haskell code, but join is well defined using dynamic dispatch.  However, dynamic dispatch has some limitations:

1. Ruby doesn't support multiple dispatch, so which method is invoked depends on only the receiver (in the above code, merge is implemented using double-dispatch techniques).
2. Dynamic dispatch doesn't work on recursive data structure.

2 is more critical.  For example. it's hard to implement balancing of red-black trees using dynamic dispatch.

Kazuki Tsujimoto has implemented pattern-match to support pattern matching in Ruby.  Balancing of red-black trees can be implemented using pattern-match as follows:

Node = Struct.new(:left, :key, :right)
class R < Node; end
class B < Node; end

def balance(left, key, right)
  match([left, key, right]) {
    with(_[R.(a, x, b), y, R.(c, z, d)]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_[R.(R.(a, x, b), y, c), z, d]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_[R.(a, x, R.(b, y, c)), z, d]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_[a, x, R.(b, y, R.(c, z, d))]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_[a, x, R.(R.(b, y, c), z, d)]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_) { B[left, key, right] }
  }
end

With Refinements, you don't need to use ugly .():

def balance(left, key, right)
  match([left, key, right]) {
    with(_[R[a, x, b], y, R[c, z, d]]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_[R[R[a, x, b], y, c], z, d]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_[R[a, x, R[b, y, c]], z, d]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_[a, x, R[b, y, R[c, z, d]]]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_[a, x, R[R[b, y, c], z, d]]) { R[B[a, x, b], y, B[c, z, d]] }
    with(_) { B[left, key, right] }
  }
end

But balance is defined as a function, not as a method, and it doesn't look so Rubyish. Is there any object-oriented way to define balance?