Skip to content

Instantly share code, notes, and snippets.

@adomokos
Last active November 14, 2016 00:42
Show Gist options
  • Save adomokos/3182e9914ab29b5a36c444a16ae7ecd1 to your computer and use it in GitHub Desktop.
Save adomokos/3182e9914ab29b5a36c444a16ae7ecd1 to your computer and use it in GitHub Desktop.
Recursion Done Right - blog post full 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
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment