Tuesday, 29 August, 2017 UTC
Summary
Iterators
Iterators are a language-independent protocol to traverse a collection of elements. It abstracts away the intricacies of the underlying collection. Despite Arrays being the primary way to store a collection of data in JS, there are many other structures, each with their own strengths and weaknesses.
Interestingly, while the principles of the iterator protocol are universally applicable to most languages, some others, for example, Java, embrace it more deeply. Most likely because its standard library readily provides multiple List, Stack, Queue, and Tree implementations, while in JS we only have Arrays, and just only more recently, Sets and Maps.
It’s also surprisingly hard to find a decent third-party library that provides these structures, let alone embrace the now-standard iteration protocol. No wonder why Java programmers are more algorithmically conscious.
Basics
An iterator is a stream of elements, and we don’t care how they are produced. Since JS uses duck typing, making an object an iterator is a matter of having a conforming
next function, that returns an object like {value: ..., done: bool}. The value is the next element, and done indicates if the end of the iterator is reached.The following object is a valid iterator that returns 1, 2, then 3 (Try it):
let num = 0; const it = { next: () => { return num < 3 ? {value: ++num, done: false} : {done: true}; } } console.log(it.next()); // {value: 1, done: false} console.log(it.next()); // {value: 2, done: false} console.log(it.next()); // {value: 3, done: false} console.log(it.next()); // {done: true}Two important things to notice here.
First, the
done: true comes after the last element. This is because the iterator might need to evaluate some more elements to realize there are no more to output. For example, consider an iterator that outputs all primes less than 10. After 7, it needs to check 8 and 9 to see that 7 was the last one.Second, iterators have state. That is, when an iterator is used once, they can not be used again. Think of them as one-shot traversal over a collection.
Making iterators
A simple function that returns an iterator for an array (without taking advantage that arrays are iterables, which will be covered in the next post) (Try it):
const iterate = (array) => { let current = 0; return { next() => { return current < array.length ? {value: array[current++], done: false} : {done: true}; } }; }And use it like:
const arr = [1, 2, 3]; const it = iterate(arr); it.next() // {value: 1, done: false} it.next() // {value: 2, done: false} it.next() // {value: 3, done: false} it.next() // {done: true}In day to day programming, iterators can be recreated if needed. For example, iteration over an array multiple times is possible.
In some rare cases, iterators can not be reproduced. For example, for a function that returns a stream of numbers starting from the current timestamp:
const makeIterator = () => { let current = new Date().getTime(); return { next: () => ({value: current++, done: false}) } }In this case, no two iterators output the same set of elements.
The last example showed that iterators can be infinite, as it never returns
{done: true}. This is something traditional arrays can not achieve. On the other hand, it’s easy to make infinite loops, like this:const it = makeIterator(); while(!it.next().done) { // infinite loop ... }It’s always a best practice to break the loop at some point if you expect a possibly infinite iterator.
Conclusion
Iterators are a powerful concept, yet they are underutilized in JS.
In the form we’ve discussed in this post they are tedious to use. In the next post, you’ll learn the basics of iterables and the language constructs that support them.