Create a gist now

Instantly share code, notes, and snippets.

@adomokos /collections_spec.rb Secret
Last active Nov 14, 2016

What would you like to do?
Recursion Done Right - blog post examples
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment