# Infinite Sequences in Ruby

## Treat your algorithms like enumerables with Enumerator

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.