Recursion Done Right - blog post examples

collections_spec.rb

module Collections
  def self.maximum((head, *tail))
    return 0 if tail.empty?
    max head, (maximum tail)
  end

  def self.max(a, b)
    a > b ? a : b
  end
  private_class_method :max

  def self.map(f, (head, *tail))
    return [] unless head

    [f.(head)] + map(f, tail)
  end

  def self.filter(f, (head, *tail))
    return [] unless head

    if f.(head)
      [head] + filter(f, tail)
    else
      filter(f, tail)
    end
  end

  def self.quicksort((head, *tail))
    return [] unless head

    smaller_sorted = quicksort(Collections.filter(->(x) { x <= head }, tail))
    bigger_sorted = quicksort(Collections.filter(->(x) { x > head }, tail))
    smaller_sorted + [head] + bigger_sorted
  end
end

RSpec.describe 'Recursion done right' do
  context 'maximum' do
    it 'returns an empty array as max of empty list' do
      expect(Collections.maximum([])).to eq(0)
    end
    it 'returns the maximum of a list' do
      expect(Collections.maximum([1,3,2])).to eq(3)
    end
  end
  context 'map' do
    it 'mapping [] with (*3) gives []' do
      expect(Collections.map(->(x){ x*3 }, [])).to be_empty
    end
    it 'mapping [1,2,3] with (*3) gives [1,6,9]' do
      expect(Collections.map(->(x){ x*3 }, [1,2,3])).to eq([3,6,9])
    end
  end
  context 'quicksort' do
    it 'returns an empty list for empty list' do
      expect(Collections.quicksort([])).to be_empty
    end
    it 'sorts a list of items' do
      expect(Collections.quicksort([2,5,3])).to eq([2,3,5])
    end
  end
  context 'filter' do
    specify 'filter (>2) [] returns an empty list' do
      expect(Collections.filter(->(x){ x > 2 }, [])).to be_empty
    end
    specify 'filter (>2) [1,3,5] returns [3,5]' do
      expect(Collections.filter(->(x){ x > 2 }, [1,3,5])).to eq([3,5])
    end
  end
end