Iterators in Typescript
Tags: javascript, typescript, webdev
Published: 2020-12-23 13:29:39

In this post I will be explaining what iterators and iterables are in Javascript/Typescript as well two examples of how you can build these structures.

# Introduction

Let's begin by demonstrating when you might need an iterator. Suppose you are implementing a data structure that can be iterated upon, let's say a tuple (fixed-length array). Your users will most likely want to transverse through the tuple by the usual order (first position, second position and so on...), so how would they do that? An example would be:

![Naive implementation](https://dev-to-uploads.s3.amazonaws.com/i/zeozd44m1adya8xmentd.png)

This approach is very bad! Our user needs to know implementation details to know how to iterate though the tuple. It also doesn't offer any protection, there are no safeguards against misuse of our tuple, e.g accessing a non-existing index of the value array. Furthermore, if we are not careful in the `getValues` method, we may allow our users to mutate the internals of our class since when returning an array we are effectively returning only a reference to said array. 

![Problem with naive implementation](https://dev-to-uploads.s3.amazonaws.com/i/pyrfjhdqfi5y6lwm90jc.png)

We can avoid this error by cloning the array so that any changes we make to the array outside of the Tuple class will not be reflected to the internal representation in our class, but this approach is very bad for performance and memory usage.

We may solve the problems above by implementing a `getValue` method which returns a value of the tuple according to some private state. 

![A better implementation](https://dev-to-uploads.s3.amazonaws.com/i/gfk186l2mnc3iv8ects8.png)

This way is more safer than the previous implementation, but we will need to implement some method to allow resetting the iteration. This reset necessity is error prone, since we may forget to reset the index at the end of an iteration and get some unexpected behavior when doing another unrelated iteration. Another problem is: what we should do when calling `getValue` more times than there are elements in the tuple without resetting the index? In the implementation above I threw an error, but this might not be the best decision. We could return another value (like undefined) but this also is problematic, see [Clean Code](https://www.amazon.com/Clean-Code-Handbook-Software-Craftsmanship/dp/0132350882), and should be avoided whenever possible.

We can effectively solve these problems utilizing iterators.

# Iterators

Conceptually, an **iterator** is an object that allows us to transverse some container (lists, arrays, ...). In Javascript this concepts translates to any *Object* that contains a `next()` method that returns an *Object* with the properties:
- value: the next value in the iteration sequence. If present when `done === true`, then it is the iterator's *return value*.
- done: a boolean which indicates if the sequence has finished or not.

After an iterator returns an *Object* with `done === true` and its return value, any additional calls to `next()` should simply return `{done: true}`.

In Typescript, we need to include at least `es2015` in the `lib` options of our `tsconfig.json` to have type support for iterators and iterables. We have the following interface for an iterator:

![Iterator interface](https://dev-to-uploads.s3.amazonaws.com/i/0dzd0u79c4lpcb7sqdsv.png)

Notice that you can pass arguments to `next()`, however this is not usual.

There are two other optional methods in the iterator interface, `return` and `throw`. Basically, `return` allows you to signal to the iterator that it should complete (setting done to *true*) and return its return value. Throw allows you to pass an error to the iterator which it may know how to handle. These two methods are more useful when you are dealing not with basic iterator but instead with a *generator*. I will explore *generators* in another post.

# Iterables

An **iterable** is any object which implements the `@@iterator` method. This means that the object (or any object in it's prototype chain) must have a method, indexed by the `Symbol.iterator` key, that returns an iterator. `Symbol.iterator` is a a well-known Symbol, meaning that it is a built-in Symbol used internally by JS engine, `for... of` for example uses `Symbol.iterator`. You can think that an iterable is any object that you can iterate with a `for... of` loop.

![Iterable interface](https://dev-to-uploads.s3.amazonaws.com/i/bs9qvh0xys31455em1fk.png)

Many JS built-in data structures are iterables, such as `Arrays, Maps and Sets`. Notice, however, that `Object` isn't an iterable by default. Note that an iterable may have multiple iterators. In this (unusual) situation we define the *default* iterator as the one returned by `Symbol.iterator()`.

Besides the iterable interface, we have another interface called **IterableIteror**. This is useful for *generators*.

![IterableIterator interface](https://dev-to-uploads.s3.amazonaws.com/i/i7yi5yg2nehpgac4b8as.png)

# Example: Tuple

We will now see how we can implement an *iterator* for our Tuple example. While it is a simple example, it gives us an idea on how we may tackle harder scenarios.

![Tuple implementation](https://dev-to-uploads.s3.amazonaws.com/i/92li5www1jdmep415pah.png)

Look how simple our Tuple is. We effectively separated the logic and state of transversing the structure from the tuple itself. The `TupleIterator` implementation is the following:

![TupleIterator implementation](https://dev-to-uploads.s3.amazonaws.com/i/gpns52wz1xqw1yulxv4w.png)

First we need to initialize the control states, `index` and `done`. Whenever the user calls `next`, we check to see if the iterator is completed and if yes we simply return `{done: true}`. 

If we have reached the end of the tuple, return the length of the tuple as the *return value* while setting `done` to *true*. This is an example of how you can use the *return value*. We could have returned `undefined` as well without a problem, it is up to you to decide what to return. In a more complex structure, we could allow the user to cancel the iteration process (through the `return` method) and return how many items were iterated upon.

If the two if's above are false, then we just get the next value and update our index for the next iteration.

Notice how we solved the problems we pointed during the introduction, we aren't exposing any Tuple's internal representation to our user, they can't unsafely modify the representation (actually they can because of Typescript `private` keyword only enforces privacy at compile time, if we want to truly enforce privacy then we can use the proposal for [private fields](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Classes/Private_class_fields)). 

Our Tuple class is simple and only contains what matters, we would only need to implement a method to get an individual value of the tuple given an index to really have something usable. If we ever want to change the iteration logic, we can extend the class and override the `@@iterator` method to return another type of iterator while maintaining everything else the same.

To use our implementation, it is as simple as the following:

![Using our implementation](https://dev-to-uploads.s3.amazonaws.com/i/850nlwso62mstey42wc9.png)

# Example: BFS in a binary tree

In this example, we will see an implementation of the [breadth-first search](https://en.wikipedia.org/wiki/Breadth-first_search) algorithm on a binary tree using iterators. This is just for illustration purposes, in the real world it would be better to implement this as a generator.

First we will define our binary tree:

![Binary tree implementation](https://dev-to-uploads.s3.amazonaws.com/i/izr4g3ow5582g68qlykm.png)

Very simple implementation, each node contains a value and up to two children. Our tree is just a wrapper around the root node, we could implement insertion and other operations but I won't in order to not pollute the example.

Now for our iterator:

![Bfs Iterator](https://dev-to-uploads.s3.amazonaws.com/i/tytez9lbpvxklnflpv16.png)

Our iterator receives a node from the tree and does some basic initialization. We will return the number of nodes iterated in the process as *return value* of our iterator, so we need to keep track of this in the `numberOfNodes` variable.

The `currentRow` variable is an array that will save the currentRow we are iterating. Usually when implementing BFS, we use a queue, but to avoid installing a dependency or implementing another structure to our example, our iterator simply saves a row and when needed gets another row via the `getNewRow` method (requires *ES2019* for the `Array.flat()`). This is good enough for our purposes.

The bulk of our iterator is the `next()` method. First we check if the iterator is completed and if not check if we reached the end of our current row. If positive, then get another row and check is this new row isn't empty. If yes then our iteration is completed, set the flag and return the number of nodes that were iterated upon. If the iteration isn't completed, then get the next value and update our local index and node counter.

As an exercise, feel free to implement a [depth-first search](https://en.wikipedia.org/wiki/Depth-first_search) iterator in our tree.

# Conclusion

Although iterators are old (they appeared in 2015) many people don't use/known them. Iterators are the building blocks for *generators* with which we can build some cool stuff, like *cancelable asynchronous functions* and [coroutines](https://en.wikipedia.org/wiki/Coroutine). In fact, when the `async/await` syntax didn't exist, people emulated it with generators. I will cover generators in my next post, until then stay safe and happy Christmas!