Recursion Done Right - blog post full 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

  def self.replicate(n, what)
    return [] if n == 0
    [what] + replicate(n-1, what)
  end

  def self.take(x, (head, *tail))
    return [] if x == 0
    [head] + take(x-1, tail)
  end

  def self.reverse((head, *tail))
    return [] if head.nil?

    reverse(tail) + [head]
  end

  def self.repeat(x, times=100)
    return [] if times.zero?
    [x] + repeat(x, times-1)
  end

  def self.zip((xhead, *xtail), (yhead, *ytail))
    return [] unless xhead
    return [] unless yhead
    [[xhead,yhead]] + zip(xtail, ytail)
  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 'quick sort' do
    it 'returns an empty list for empty list' do
      expect(Collections.quicksort([])).to eq([])
    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

  context 'replicate' do
    it 'repeats the item x times' do
      expect(Collections.replicate(0, 'a')).to be_empty
      expect(Collections.replicate(5, 'a')).to eq(['a','a','a','a','a'])
    end
  end
  context 'take' do
    it 'takes x number of items from a list' do
      expect(Collections.take(0, [1,2])).to be_empty
      expect(Collections.take(3, (1..5).to_a)).to eq([1,2,3])
    end
  end
  context 'reverse' do
    it 'reverses a list' do
      expect(Collections.reverse([])).to be_empty
      expect(Collections.reverse([3,2,1])).to eq([1,2,3])
    end
  end
  context 'repeat' do
    it 'repeats the item' do
      expect(Collections.take(3, Collections.repeat('a'))).to eq(['a','a','a'])
    end
  end
  context 'zip' do
    it 'zips two arrays together' do
      expect(Collections.zip([1,2,3],['a','b'])).to eq([[1,'a'],[2,'b']])
    end
  end
end