Enumerator 1 2 3

Functional languages like Clojure have sequences. Sequences are pretty amazing: they let us treat algorithms as data structures. We can call functions on the data as it is produced, allowing us to interact with the results like a collection even when the sequence is infinite.

The Ruby standard library doesn’t have an official sequence class or module, but we can get pretty far with the Enumerable module. Rubyists are typically introduced to Enumerable through methods on Array, like #map and #select. Arrays like [1,2,3,4] may be thought of as finite, eagerly loaded sequences; they already contains all the members we want to enumerate with methods. We can also extend this API to sequences like “give me multiples of 5” in Ruby.

Enumerable Fibonacci

Consider an infinite sequence like fibonacci. We could create a method that generates the first n fibonacci members given n as a paramter. This implementation could look like this:

def eager_fibonacci(n)
  a = b = 1
  result = []

  loop do
    break if result.size >= n

    result << a
    a, b = b, a + b
  end

  result
end

This works, but we can go one step further. Instead of returning an eagerly-loaded array, we can return an Enumerator. We'll yield each member to the Enumerator as it is generated.

def fibonacci
  Enumerator.new do |y|
    a = b = 1

    loop do
      y << a
      a, b = b, a + b
    end
  end
end

What the heck is an Enumerator? It’s an enumerable object that can be used for either internal or external enumeration of a collection - for more details, check out my previous post. The Enumerator initialize method take a block that acts like a template for an enumerable algorithm. The block takes a parameter, y, which is an instance of an Enumerator::Yielder, which let's us yield each member of the Enumerator to blocks passed to Enumerable method calls. In short, this means we can treat an Enumerator like an Array, though we can also do so much more.

To retrieve the first ten members of our enumerable fibonacci method, we’d instead do something like:

fibonacci.take(10)

We can still enumerate over the fibonacci sequence as before:

fibonacci.take(10).each { |i| puts i }

Using the Enumerator#lazy method, we can avoid eager enumeration and run queries or calculations as each member is generated. This opens the door to some interesting use cases, like the following:

fibonacci.lazy.select(&:even?).first(10)
#=> [2, 8, 34, 144, 610, 2584, 10946, 46368, 196418, 832040]

fibonacci.lazy.select(&:odd?).first(10)
#=> [1, 1, 3, 5, 13, 21, 55, 89, 233, 377]

We can filter for the first 10 even or odd numbers generated by fibonacci. Inserting the with_index enumerator method, we can see how many items we need to enumerate to get either the first 10 even or odd numbers:

fibonacci.lazy.with_index.select { |n, i| n.odd? }.first(10)
#=> [[1, 0], [1, 1], [3, 3], [5, 4], [13, 6], [21, 7], [55, 9], [89, 10], [233, 12], [377, 13]]

fibonacci.lazy.with_index.select { |n, i| n.even? }.first(10)
#=> [[2, 2], [8, 5], [34, 8], [144, 11], [610, 14], [2584, 17], [10946, 20], [46368, 23], [196418, 26], [832040, 29]]

Notice we only need to enumerate 13 items to retrieve 10 odd numbers from fibonacci, while 29 are needed to retrieve the first 10 evens. These results wouldn’t be easily achieved with our previous fibonacci implementation in which the number of desired members must be known ahead of time.

Try creating other numerical sequences with enumerators on your own, like multiples of n, factorials for the first n integers or enumerating sums of squares. Also be sure to check out Pat Shaughnessy's great primer on lazy enumerators.

Sequence Functions

Clojure also has a number of useful functions that allow us to generate sequences from other functions. Let’s look at repeatedly which simply calls the given function over and over, emitting the results as a sequence. To get a sequence of five random numbers between 0 - 100:

(take 5 (repeatedly #(rand-int 100)))

For those new to Clojure, the syntax may look odd, but this expression "takes the first 5 results of repeatedly asking for a random integer of 0 to 100" and returns a sequence.

We can use Ruby enumerators to do something similar in Ruby. Let’s create our own version of repeatedly, which takes a will call a given block over and over again. Let's start with a naive implementation which use a loop:

def repeatedly_foo(&block)
 loop do
    block.call
  end
end

This method is not useful because the function will never return; it's an infinite loop! You’ll have to issue a kill signal to stop the execution (Ctrl-C!). We could give repeatedly_foo a limit n and break out of the loop with a counter.

def repeatedly_foo(n, &block)
  result = []

  loop do
    break if result.size >= n

    result << block.call
  end

  result
end

This is an improvement, but like our fibonacci example earlier, it means we need to load the desired number eagerly in the result array and have less control over the results.

Again, we'll wrap the loop in an Enumerator so we can treat the result as a sequence. We’ll “yield” the result of calling the block to the Enumerator::Yielder object (the y << block.call) expression in our loop:

def repeatedly(&block)
  Enumerator.new do |y|
    loop do
      y << block.call # "yield" the result to the Enumerator::Yielder
    end
  end
end

We now have an abstraction that can be chained to other enumerator methods. It also has a similar terse feel to the Clojure inspiration we saw earlier.

repeatedly { rand(100) }.take(5)
#=> [48, 48, 72, 41, 70] # your results will vary... they're random!

To Infinity and Beyond

Of course, sequences of numbers aren't the only concept that can be modeled this way in Ruby. Any collection of unknown size, for example, results from a search query, paginated resources from an API client library, data from a web crawl, etc., are also great use cases for exposure as enumerables. Consider wrapping your generated collections in an Enumerator to provide callers with flexible, composable results.

Share this post on Twitter

Part of the Enumerable series. Published on Nov 21, 2015