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:
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.
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.
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, 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:
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.
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.
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.
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:
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).
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:
Example: BFS in a binary tree
In this example, we will see an implementation of the 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:
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:
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 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. 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!
Top comments (4)
Nice article. Interesting application of iterations for trees / search algorithms rather simple lists or arrays.
Perhaps you're bringing it up in the next post about generators as they might be more applicable for this point, but I also think being able to expose parts of that data that are needed instead of all of it is very beneficial for both memory and execution costs. For example, if the producer function returns an array or list and has many items say 50 but the consumer only needs the first few say 3, the producer still has to the whole thing and then take the first three from it, but if it's an iterator the consumer can control how many times it calls next(). If this is some expensive data source it might be useful.
I'm not sure if you preferred to split
mapandflatbut the later typescript hasflatMapsince it's such a common operation.Is there a way to present the code differently that isn't an image? The images seems small I have to click to see the full size and you can't copy bits or pieces to play with. I think it would make it much more pleasing to read.
Yeah, being able to expose parts of the data is a useful application, I didn't think of that.
I didn't know about
flatMap, thanks for presenting me hahaI've been experimenting with images and with normal markdown code sections. Yeah, not being able to copy code is a pain, I will probably stick with markdown code sections for now on. Thanks for the feedback!
You should talk about generators too. Generators in JavaScript are the simplest and sugar way to implement an iterator.
Yes, my next post will be about generators. I didn't include them in this one because the text would be too long.