Apply-Algorithm in Ruby

apply.rb

#!/usr/bin/env ruby

class Node
  attr_accessor :label
  attr_accessor :lo
  attr_accessor :hi

  def initialize(lo, label, hi)
    @lo = lo
    @label = label
    @hi = hi
  end

  def terminal?
    lo.nil? && hi.nil?
  end

  def to_s
    "(#{lo.to_s},#{label},#{hi.to_s})"
  end
end

class Terminal < Node
  def initialize(label)
    super(nil, label, nil)
  end

  def to_s
    label.to_s
  end
end

def apply(function, f, g)
  if f.terminal? && g.terminal?
    # Case I
    Terminal.new(function.call(f.label, g.label))
  elsif !f.terminal? && !g.terminal? && f.label == g.label
    # Case II
    Node.new(
      apply(function, f.lo, g.lo),
      f.label,
      apply(function, f.hi, g.hi)
    )
  elsif !f.terminal? && (g.terminal? || g.label > f.label)
    # Case III
    Node.new(
      apply(function, f.lo, g),
      f.label,
      apply(function, f.hi, g)
    )
  elsif !g.terminal? && (f.terminal? || f.label > g.label)
    # Case IV
    Node.new(
      apply(function, f, g.lo),
      g.label,
      apply(function, f, g.hi)
    )
  end
end


# apply(·, Bg[1/x], Bg)
bg_x_is_1 = Node.new(Terminal.new(0), :y, Terminal.new(1))
bg = Node.new(Node.new(Terminal.new(0), :z, Terminal.new(1)), :x, Node.new(Terminal.new(0), :y, Terminal.new(1)))


bgf = Node.new(Node.new(Terminal.new(1), :z, Terminal.new(0)), :y, Node.new(Terminal.new(0), :z, Terminal.new(1)))
bgg = Node.new(Node.new(Terminal.new(1), :y, Terminal.new(0)), :x, Terminal.new(0))

puts apply(->(a, b) { a | b }, bgf, bgg)