From: Jim Weirich <jim@...>
Date: 2004-08-27T11:07:09+09:00
Subject: Re: python generators to ruby closures, help

--------------080802090605060207000206
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit

William Morgan wrote:
> 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    jim@weirichhouse.org     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)

--------------080802090605060207000206
Content-Type: text/plain;
 name="enumpipe.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="enumpipe.rb"

#!/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

--------------080802090605060207000206
Content-Type: text/plain;
 name="testenumpipe.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="testenumpipe.rb"

#!/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

--------------080802090605060207000206--