Friday, February 02, 2007

Ruby Streams

I've been thinking about my business days problem some more. And this time I turned to Ruby, a language which I am becoming quite familiar with.

This is my naive implementation of streams in Ruby. Streams are thus functions. The actual class name is 'Proc', a lambda returns a 'Proc'. Each call returns a new value.

def stream_from(value)
lambda {value = value.succ}
end

class Proc
def filter
f = lambda do
value = self.call
return (yield(value) ? value : f.call)
end
end

def take(n)
result = []
n.times {result << self.call}
return result
end
end
As for "filter", it takes a predicate passed as block. The filter becomes a "decorator" for the stream.

This is a nice example of closures. The 'value' parameters becomes the state for the stream. Also of note, the use of the variable 'f' to fake recursion of an anonymous function.

Prints the 20 next business days:

s = stream_from(Date.today).filter {|date| date.cwday < 6}

puts s.take(20)

Note that my "contract" with stream_from is that what I pass it implements succ. Here's an example with integer:

s = stream_from(4)

puts s.take(20)

And, of course, filters can be chained. The next Monday that falls on a 17th:

s = stream_from(Date.today).filter {|date| date.day == 17}.filter {|date| date.cwday == 1}

puts s.call.to_s

Here's the same code as before, but with a function cast as a block:

def monday?(date)
date.cwday == 1
end

s = stream_from(Date.today).filter {|date| date.day == 17}.filter(&method(:monday?))

I decided consciously to avoid optimizations here. It did keep my code short and clean. Besides, you should only optimize based on need.

There's much more to streams... combining streams together, maps, more complicated generation of the next value, etc.

So, here's your next interview questions:

"What's the first 3 prime numbers after 5,000,000,000 which has a 3 as last digit?"

s = stream_from(5_000_000_000).filter{|x| x.prime?}.filter{|x| x.mod(10) == 3}

puts s.take(3)

I leave the code for "prime?" to your imagination.

The concept of command-line pipes springs to mind. One of the reason the command line is so powerful, is that you can combine filters together to perform truly complicated tasks. Another reason is that each filter does only one thing and does it well.

It's all about thinking in pipes.

2 Comments:

Blogger jeff said...

beautiful little bit of code there.

6:01 PM  
Anonymous Saimon Moore said...

very handy, thanks...

9:36 AM  

Post a Comment

<< Home