How to remove an array from another in Ruby, functional style (no data structure is mutable)

subtract_array.rb

module FunctionalArrayExtension
  def head
    _split_it
    raise StandardError, "cannot take head of an empty array" if empty?
    @head
  end

  def tail
    _split_it
    raise StandardError, "cannot take tail of an empty array" if empty?
    @tail
  end

  private

  def _split_it
    unless @split_already
      @head, *@tail = *self
      @split_already = true
    end
  end
end

module ArrayExtension
  # entry point for recursive function
  def subtract(other)
    _sub(self.sort, other.sort, [])
  end

  private

  def _sub(p, q, a)
    # because p and q are sorted, it is cheap to check
    # if an item should be saved (added to accumulator)
    # or filtered away
    if q.empty? # done filtering, return accumulator + what is left in p
      a + p
    else
      if p.head > q.head
        _sub(p, q.tail, a + [p.head])
      else
        p.head == q.head ? _sub(p.tail, q.tail, a) : _sub(p.tail, q, a + [p.head])
      end
    end
  end
end

require 'rspec'

describe "Array subtract" do
  Array.send(:include, FunctionalArrayExtension)
  Array.send(:include, ArrayExtension)

  def frozen(*ary)
    ary.freeze
  end

  it "should remove nothing if there is nothing to remove" do
    a = [1, 3, 2]
    a.subtract([]).should == a.sort
  end

  it "should remove nothing if there is nothing to remove from" do
    [].subtract([]).should == []
  end

  it "should remove matching elements without modifying array" do
    a = frozen(1, 3, 2)
    b = frozen(3)

    a.subtract(b).should == [1, 2]
  end

  it "should remove only one element for each matching element" do
    a = frozen(3, 3, 3, 2, 2)
    b = frozen(2, 3)

    a.subtract(b).should == [2, 3, 3]
  end

  it "should include all elements not in subtractor" do
    a = frozen(4, 2, 3, 1)
    b = frozen(2, 3)

    a.subtract(b).should == [1, 4]
  end
end