Ruby: Manipulate Iterators?

Question

I'm having teething problems with Ruby, with regards to creating single-direction, lazily-evaluated, potentially-infinite iterators. Basically, I'm trying to use Ruby like I'd use Haskell lists and, to a lesser extent, Python generators.

It isn't that I don't understand them per se; I just don't know how to use them as casually as other languages, and I'm also unsure about what methods in Ruby will turn them into arrays behind my back, unloading the entire sequence into memory unnecessarily.

And yes, I've been studying the Ruby reference manual. For half an hour in fact, attentively. Or perhaps evidently not.

For example, if I were to implement a card deck, it would look something like this in Python (untested):

# Python 3

from itertools import chain, count

face_ranks =
    dict(
        zip(
            ('jack', 'queen', 'king', 'ace'),
            count(11)))

sorted_deck =
    map(
        lambda suit:
            map(
                lambda rank:
                    {
                        'rank' : rank,
                        'suit' : suit
                    },
                chain(
                    range(2, 11),
                    face_ranks.keys())),
        ('clubs', 'diamonds', 'hearts', 'spades'))

So, how would I do this in Ruby, completely avoiding arrays? Note that the above code uses, to my knowledge, only tuples and generators: at no point is the whole sequence dumped into memory like if I had used an array. I could be wrong about the above code, but you get what I want.

How do I chain iterators (like Python's chain())? How do I generate an iterator of an infinite range (like Python's count())? How can I add an array to an iterator (like passing a tuple to Python's chain()) without converting the whole thing to an array in the process?

I've seen solutions, but they involve arrays or unnecessary complexities like fibers.

In Python I can manipulate and throw around iterators with the same simplicity as arrays. I can almost treat them like Haskell lists, which I'm most comfortable with, and is really what I think in when coding. I'm not comfortable with Ruby arrays, which is why I seek help with its alternative(s).

I've managed to pick up nuggets of information on the internet about it, but I couldn't find any that covers basic manipulation of such data structures in Ruby? Any help?

Answer 1

Ruby doesn't seem to have a lot of built-in methods for doing the different things you wanted to do with enumerators, but you can make your own methods. That's what I did here, using Ruby 1.9:

iter.rb

def get_enums_from_args(args)
  args.collect { |e| e.is_a?(Enumerator) ? e.dup : e.to_enum }
end

def build(y, &block)
  while true
    y << (begin yield; rescue StopIteration; break; end)
  end
end

def zip(*args)
  enums = get_enums_from_args args
  Enumerator.new do |y|
    build y do
      enums.collect { |e| e.next }
    end
  end
end

def chain(*args)
  enums = get_enums_from_args args
  Enumerator.new do |y|
    enums.each do |e|
      build y do
        e.next
      end
    end
  end
end

def multiply(*args)
  enums = get_enums_from_args args
  duped_enums = enums.collect { |e| e.dup }
  Enumerator.new do |y|
    begin
      while true
        y << (begin; enums.collect { |e| e.peek }; rescue StopIteration; break; end )

        index = enums.length - 1
        while true
          begin
            enums[index].next
            enums[index].peek
            break
          rescue StopIteration
            # Some iterator ran out of items.

            # If it was the first iterator, we are done,
            raise if index == 0

            # If it was a different iterator, reset it
            # and then look at the iterator before it.
            enums[index] = duped_enums[index].dup
            index -= 1
          end
        end
      end
    rescue StopIteration
    end
  end
end

And I wrote a spec using rspec to test the functions and demonstrate what they do:

iter_spec.rb:

require_relative 'iter'

describe "zip" do
  it "zips together enumerators" do
    e1 = "Louis".chars
    e2 = "198".chars
    zip(e1,e2).to_a.should == [ ['L','1'], ['o','9'], ['u','8'] ]
  end

  it "works with arrays too" do
    zip([1,2], [:a, nil]).to_a.should == [ [1,:a], [2,nil] ]
  end
end

describe "chain" do
  it "chains enumerators" do
    e1 = "Jon".chars
    e2 = 0..99999999999
    e = chain(e1, e2)
    e.next.should == "J"
    e.next.should == "o"
    e.next.should == "n"
    e.next.should == 0
    e.next.should == 1
  end
end

describe "multiply" do
  it "multiplies enumerators" do
    e1 = "ABC".chars
    e2 = 1..3
    multiply(e1, e2).to_a.should == [["A", 1], ["A", 2], ["A", 3], ["B", 1], ["B", 2], ["B", 3], ["C", 1], ["C", 2], ["C", 3]]
  end

  it "is lazily evalutated" do
    e1 = 0..999999999
    e2 = 1..3
    e = multiply(e1, e2)
    e.next.should == [0, 1]
    e.next.should == [0, 2]
    e.next.should == [0, 3]
    e.next.should == [1, 1]
    e.next.should == [1, 2]
  end

  it "resulting enumerator can not be cloned effectively" do
    ranks = chain(2..10, [:jack, :queen, :king, :ace])
    suits = [:clubs, :diamonds, :hearts, :spades]
    cards = multiply(suits, ranks)
    c2 = cards.clone
    cards.next.should == [:clubs, 2]
    c2.next.should == [:clubs, 2]
    c2.next.should == [:clubs, 3]
    c2.next.should == [:clubs, 4]
    c2.next.should == [:clubs, 5]
    cards.next.should == [:clubs, 6]
  end

  it "resulting enumerator can not be duplicated after first item is evaluated" do
    ranks = chain(2..10, [:jack, :queen, :king, :ace])
    suits = [:clubs, :diamonds, :hearts, :spades]
    cards = multiply(ranks, suits)
    cards.peek
    lambda { cards.dup }.should raise_error TypeError
  end
end

As shown in the specs above, these methods use lazy evaluation.

Also, the major weakness of the zip, chain, and multiply functions defined here is that the resulting enumerator can not be easily duplicated or cloned because we haven't written any code to duplicate the enum arguments that these new enumerators rely on. You would probably need to make a subclass of Enumerator or make a class the includes the Enumerable module or something like that to make dup work nicely.