Conceptualizing Enumerators and Lazy Enumerators in Ruby

Question

I need a bit of help on conceptualizing Lazy Enumerator objects in Ruby.

The way I think about an Enumerator object is as a "stateful" version of a collection. The object understands what elements are part of the collection, and what the "next" element that should be yielded is. It is an object that knows that its elements are, say, 1, 2, and 3, it has already yielded 1 and 2, and it will therefore yield 3 if asked to do so.

Assuming that that conceptualization of an Enumerator is correct, I have a tough time with how a Lazy Enumerator works. A Lazy Enumerator is built off of a "regular" Enumerator, but is supposed to not calculate its set beforehand. For example, from The Ruby Way:

enum = (1..Float::INFINITY).each
lazy = enum.lazy
odds = lazy.select(&:odd)

If a Lazy Enumerator is built off of a Lazy Enumerator, then how is the Lazy Enumerator lazy, since I'm doing the Enumerator part, which is presumably not lazy, first?

Answer 1

Enumerator#lazy allows you to effectively create a chain of enumerable operations which are applied to each value as it's iterated from the enumerable. By comparison, normal enumerators perform each operation to all the values in the enumerable, then pass the result down the chain to the next operation in the chain. You can think of lazy enumerators as "depth-first" operations, and normal enumerators as "breadth-first" operations.

Normal enumerators return the result of the enumeration:

> (1..10).select(&:odd?)
 => [1, 3, 5, 7, 9]

If you were to chain these operations, you could perform some list of operations on a finite list of values:

> (1..10).select(&:odd?)
 => [1, 3, 5, 7, 9]

> (1..10).select(&:odd?).map {|v| v * 2 }
 => [2, 6, 10, 14, 18]

Each operation in the chain is applied to all the values in the enumerable before passing the list of values down the chain for the next operation.

By comparison, Enumerable#lazy returns lazy enumerators ("things to do with a value") from each operation:

> (1..10).lazy.select(&:odd?)
 => #<Enumerator::Lazy: #<Enumerator::Lazy: 1..10>:select>
> (1..10).lazy.select(&:odd?).map {|v| v * 2 }
 => #<Enumerator::Lazy: #<Enumerator::Lazy: #<Enumerator::Lazy: 1..10>:select>:map>

As you can see, it's not processing the entire list of values with each call in the chain. Instead, when you coalesce a value out of the enumerable (say, with #next), then the next value is taken from the underlying enumerable, then passed through each of the enumerable operations, and finally returned:

> (1..10).lazy.select(&:odd?).map {|v| v * 2 }.next
 => 2

If you were to try these same operations on an infinite list, then the non-lazy enumerators would stall forever, because it would attempt to do a breadth-first pass on an infinite enumerable, which will obviously never terminate!