here is how jim was thinking of it. he seems to love mixing in
Enumerable for all kinds of fun dataflow tricks, and that seemed not
such a bad idea to me.
but don't let this stifle your creativity thinking about postfix /
concatenative combinators this time around. (the terminology of
"concatenative combinators" first found me by way of the Forth
language, which then influenced the Toy language. feel free to also
browse jim cunningham's excellent programming language wiki at
c2.com).
From: Jim Weirich <
[email protected]>
Reply-To: (e-mail address removed)
To: ruby-talk ML <
[email protected]>
Date: Fri, 27 Aug 2004 11:07:09 +0900
Subject: Re: python generators to ruby closures, help
William said:
Yes. I don't think you want the Generator class at all then. As the
email you quoted said, Python generators are a solution to a problem
that Ruby doesn't have. Generators have a place in Ruby but this ain't
it.
From what I can tell, all the functionality they build up in the Python
example is just so that they can do thing that in Ruby can be done
neatly with iterators, like this:
As William pointed out, enumerator pipes can be implemented in Ruby
without resorting to continuations, and that the current enumerator
syntax is very pipe-like in many ways.
However, one thing the Python version handles that enumerator chaining
does not is an infinite enumerator. In the python examples, we have
the following construct:
Ints() | firstTen | oddNotDivBy3
Ints() is a generator that will generate all the integers (given
enough time and space). The next filter "firstTen" only takes the
first 10 of those numbers. Since the generator chain only takes a
number from a generator when it is needed, the Ints() generator is
never asked for any more than 10 number.
We can do the same with Ruby enumerators. Imagine a OddNumberFilter
object that implements a each method like this ...
class OddNumberFilter
include Enumerable
attr_accessor :source
def each
@source.each { |n| yield(n) if (n % 2) != 0 }
end
end
It uses a source enumerable to generate numbers and only yields when
it finds an odd number. We can use it like this ...
odds_only = OddNumberFilter.new
odds_only.source = (1..10)
odds_only.to_a # => [1, 3, 5, 7, 9]
Since a filter can take _any_ enumerable as a source, it can even take
other filters. Let's generalize our OddNumberFilter class to a
CondFilter class that takes a condition and only passes items that
pass the condition.
class CondFilter
include Enumerable
attr_accessor :source
def initialize(&block)
@block = block
end
def each
@source.each { |it| yield(it) if @block.call(it) }
end
end
Now we create a chain of filters ...
odds_only = CondFilter.new { |n| (n % 2) != 0 }
odds_only.source = (1..10)
divisible_by_three = CondFilter.new { |n| (n % 3) == 0 }
divisible_by_three.source = odds_only
divisible_by_three.to_a #=> [3, 9]
It works, but it is ugly. So lets create a little syntactic sugar to
get this to work ...
module Enumerable
def |(filter)
filter.source = self
filter
end
end
odds_only = CondFilter.new { |n| (n%2) != 0 }
divisible_by_three = CondFilter.new { |n| (n%3) == 0 }
pipe = (1..10) | odds_only | divisible_by_three
pipe.to_a # => [3, 9]
With this foundation, handling infinite enumerations are easy ...
class Ints
include Enumerable
def initialize
@n = 0
end
def each
loop do
yield @n
@n += 1
end
end
end
And a class to take only so many items ...
class Take
include Enumerable
attr_accessor :source
def initialize(limit)
@limit = limit
end
def each
n = 0
@source.each do |it|
n += 1
break if n > @limit
yield it
end
end
end
( Ints.new | Take.new(5) ).to_a # => [0, 1, 2, 3, 4]
From this point the File generator and the other stuff in the Python
example should be obvious.
Here's a fun puzzle. Using filters, create a Sieve of Erasothanes
filter that, given an input of Ints.new, will generate a series of
prime numbers. In other words, the code ...
( Ints.new | Primes.new | Take.new(100) ).to_a
will create an array of the first 100 prime numbers.
I've attached full examples and test suites for all the the above
(although factored a bit differently), so don't peek if you want to work
out the Primes puzzle ...
--
-- Jim Weirich (e-mail address removed)
http://onestepback.org
-----------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)
#!/usr/bin/env ruby
require 'find'
module Enumerable
def |(filter)
filter.source = self
filter
end
end
class EmptyEnumClass
include Enumerable
def each() end
end
EmptyEnum = EmptyEnumClass.new
class EnumFilter
include Enumerable
attr_reader :source
def initialize(source=nil)
@source = source || EmptyEnum
end
def source=(new_source)
case @source
when EnumFilter
@source.source = new_source
else
@source = new_source
end
end
def each(&block)
@source.each(block)
end
end
class CondFilter < EnumFilter
def initialize(&block)
super()
@block = block
end
def each
@source.each do |it| yield it if @block[it] end
end
end
class Ints
include Enumerable
def initialize
@n = 0
end
def each
loop do
yield @n
@n += 1
end
end
end
class Quit < EnumFilter
def initialize(&block)
@block = block
end
def each
@source.each do |it|
break if @block[it]
yield it
end
end
end
class Start < EnumFilter
def initialize(start)
@start = start
end
def each
@source.each do |it|
yield it if it >=
@start
end
end
end
class Take < EnumFilter
def initialize(limit)
@limit = limit
end
def each
n = 0
@source.each do |it|
break if n >= @limit
yield it
n += 1
end
end
end
class EnumFiles
include Enumerable
def initialize(fn)
@file_name = fn
end
def each
Find.find(@file_name) do |fn| yield fn end
end
end
class Primes < EnumFilter
def initialize
super
@source = Start.new(2)
end
def each
loop do
n = (@source | Take.new(1)).to_a[0]
yield n
@source = @source | new_filter(n)
end
end
def new_filter(n)
CondFilter.new { |it| (it%n) != 0 }
end
end
#!/usr/bin/env ruby
require 'test/unit'
require 'enumpipe'
class TestEnumPipe < Test::Unit::TestCase
def test_create
ep = CondFilter.new
assert ep
end
def test_odd
odd_filter = CondFilter.new { |it| (it % 2) != 0 }
odd_filter.source = (1..10)
assert_equal [1,3,5,7,9], odd_filter.to_a
end
def test_no_source
odd_filter = CondFilter.new { |it| (it % 2) != 0 }
assert_equal [], odd_filter.to_a
end
def test_two_filters
odd_filter = CondFilter.new { |it| (it % 2) != 0 }
filter_thirds = CondFilter.new { |it| (it % 3) == 0 }
odd_filter.source = (1..10)
filter_thirds.source = odd_filter
assert_equal [3, 9], filter_thirds.to_a
end
def test_left_pipeing
odd_filter = CondFilter.new { |it| (it % 2) != 0 }
filter_thirds = CondFilter.new { |it| (it % 3) == 0 }
filter_thirds.source = odd_filter
filter_thirds.source = (1..10)
assert_equal [3, 9], filter_thirds.to_a
end
def test_pipe_syntax
pipe = (1..10) | CondFilter.new { |it| (it%2) != 0 }
assert_equal [1,3,5,7,9], pipe.to_a
end
def test_pipe_three
src = (1..10)
odd = CondFilter.new { |it| (it%2) != 0 }
thirds = CondFilter.new { |it| (it%3) == 0 }
pipe = src | odd | thirds
assert_equal [3, 9], pipe.to_a
end
def test_pipe_right_associative
src = (1..10)
odd = CondFilter.new { |it| (it%2) != 0 }
thirds = CondFilter.new { |it| (it%3) == 0 }
pipe = src | (odd | thirds)
assert_equal [3, 9], pipe.to_a
end
def test_infinite_takes
pipe = Ints.new | Take.new(10)
assert_equal (0...10).to_a, pipe.to_a
end
def test_multiple_takes_on_ints
pipe = Ints.new | Take.new(2)
assert_equal [0,1], pipe.to_a
assert_equal [2,3], pipe.to_a
assert_equal [4,5], pipe.to_a
end
def test_quit_filter
pipe = Ints.new | Quit.new { |it| it > 5 }
assert_equal [0,1,2,3,4,5], pipe.to_a
end
def test_start
pipe = Ints.new | Start.new(5) | Take.new(3)
assert_equal [5,6,7], pipe.to_a
end
def test_files
files = EnumFiles.new(".")
filelist = files.to_a
assert filelist.member?("./enumpipe.rb")
assert filelist.member?("./testenumpipe.rb")
end
def test_file_filter
testfiles = EnumFiles.new('.') | CondFilter.new { |fn|
File.basename(fn) =~ /^test.*\.rb$/ }
filelist = testfiles.to_a
assert filelist.member?("./testenumpipe.rb")
end
def test_primes
primes = Ints.new | Primes.new | Take.new(10)
assert_equal [2,3,5,7,11,13,17,19,23,29], primes.to_a
end
end
