Infinite sequences in ruby

December 31st 2012

One feature of harmonia is tasks that recur on a schedule, e.g. every Thursday, or on the 30th day of each month. For these tasks we need to know not just when they’ll next occur, but also things like the next 4 occurrences, or all occurrences this month.

To do this we’ve used a technique more common in clojure: using an infinite sequence.

Defining simple infinite sequences

Ruby 1.9 and above let us define infinite sequences using the Enumerator class. A simple example is the sequence of integers:

integers = Enumerator.new do |yielder|
  n = 0
  loop do
    yielder.yield n
    n = n + 1
  end
end

>> integers.take(5)
=> [0, 1, 2, 3, 4]
>> integers.take(10)
=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Here’s how this works. The block passed to Enumerator.new defines our sequence. It takes a yielder argument with a special method #yield, used to return elements in the sequence. Whenever #yield is called, execution of the block stops. Execution only restarts if more elements are needed, making the sequence lazy. The Enumerator class handles this stopping and starting execution — we only need to worry about how to generate each element.

Most of the code above is concerned with looping and yielding values, not generating them. We can factor this out, giving us a method that makes it trivial to define new sequences:

def sequence(&generator)
  Enumerator.new do |yielder|
    n = 0
    loop do
      yielder.yield generator.call(n)
      n = n + 1
    end
  end
end

>> integers = sequence {|n| n}
>> integers.take(10)
=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

>> squares = sequence {|n| n * n}
>> squares.take(10)
=> [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

When using infinite sequences laziness is extremely important, as it’s impossible to generate all members of an infinite list in anything less than infinite time. A sequence that outputs whenever a new value is calculated shows this laziness in action:

integers = sequence {|n| puts "Calculating result #{n}"; n}

>> integers.take(3)
Calculating result 0
Calculating result 1
Calculating result 2
=> [1, 2, 3]

Now we can define sequences, how can we use them? We’ve already seen that we can #take any number of elements from our sequence. We can also use #take_while to take elements until a condition is met, such as finding all square numbers under 250:

>> squares.take_while {|n| n < 250}
=> [0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225]

In fact all Enumerable methods are available, but we have to take care in using them. As our sequences are infinite, any method that iterates over all members has the potential to take an infinite amount of time. For example calling #any? will either return true (if a matching element exists) or never return.

Another big drawback is that when we call Enumerable methods, laziness isn’t preserved. Suppose we want the first 5 odd square numbers. We might try the following:

>> squares.select {|n| n % 2 == 1}.take(5)

Unfortunately this will never return. Even though we only want a finite set of results, the call to #select operates on the full infinite sequence before it returns. #take(5) is never called. The same problem exists with #map, #drop, #reject and more.

Preserving laziness across derived sequences

Without laziness preservation, our sequences seem of limited use. In ruby 2.0 we can use #lazy to make our sequences lazier, but in 1.9 this isn’t available to us. Thankfully we can get around this by generating lazy versions of Enumerable methods ourselves. Let’s take the previous example, finding the first 5 odd square numbers. We hit a roadblock because #select never returned. If instead of using #select we use a new Enumerator to do our selecting, we can work around this:

odd_squares = Enumerator.new do |yielder|
  squares.each do |square|
    yielder.yield square if (square % 2 == 1)
  end
end

>> odd_squares.take(5)
=> [1, 9, 25, 49, 81]
>> odd_squares.take(10)
=> [1, 9, 25, 49, 81, 121, 169, 225, 289, 361]

Our new Enumerator iterates lazily through our original sequence, yielding only odd values. We’ve chained two enumerators together to preserve laziness.

This is all a bit cumbersome as is, but we can turn this into a ‘#select’ method on a new LazyEnumerator class:

class LazyEnumerator < Enumerator
  def select(&block)
    self.class.new do |yielder|
      each do |value|
        yielder.yield value if block.call(value)
      end
    end
  end
end

def lazy_sequence(&generator)
  LazyEnumerator.new do |yielder|
    n = 0
    loop do
      yielder.yield generator.call(n)
      n = n + 1
    end
  end
end

>> lazy_squares = lazy_sequence {|n| n * n}
>> lazy_squares.select {|n| n % 2 == 1}.take(5)
=> [1, 9, 25, 49, 81]

#reject and #map can be chained in a similar way to #select:

class LazyEnumerator < Enumerator
  def reject(&block)
    self.class.new do |yielder|
      each do |value|
        yielder.yield value unless block.call(value)
      end
    end
  end

  def map(&block)
    self.class.new do |yielder|
      each do |value|
        yielder.yield block.call(value)
      end
    end
  end
end

#drop and #drop_while are slightly more complicated, but follow a similar pattern. The main difference being that they need to keep track of how much to drop:

class LazyEnumerator < Enumerator
  def drop(n)
    self.class.new do |yielder|
      dropped_enough = false
      dropped = 0
      each do |element, index|
        dropped_enough ||= dropped >= n
        yielder.yield element if dropped_enough
        dropped = dropped + 1
      end
    end
  end

  def drop_while(&block)
    self.class.new do |yielder|
      match_found = false
      each do |element|
        match_found ||= !block.call(element)
        yielder.yield element if match_found
      end
    end
  end
end

Together, these methods give us a LazyEnumerator that can be chained in a great number of ways, giving our sequences a lot of power. #take and #drop let us select which members of a sequence we’re interested, while #select, #reject and #map allow us to build new sequences from existing ones:

>> integers = lazy_sequence {|n| n}
>> squares = integers.map {|n| n * n }
>> odd_squares = squares.select {|n| n % 2 == 1}
>> odd_squares.drop(10).take(10)
=> [441, 529, 625, 729, 841, 961, 1089, 1225, 1369, 1521]

Using only a few simple methods, we’ve been able to answer a complicated (though contrived) question, what are the second ten odd square numbers? This particular answer may not be interesting, but the technique of defining and deriving infinite sequences is much more general and useful. This is only a small sample of what you can do with them.