JavaScript lazy evaluation: Iterables & Iterators

MelkorNemesis

Sep 7 · 5 min read

Image for post

JavaScript lazy evaluation: Iterables & Iterators

Lazy evaluation, every functional programmer’s wet dream. Soon enough, we will look at generators. But first, let’s get a grasp of what iterators and iterables are because to me, they’re a prerequisite for generators.

Lazy evaluation

Lazy evaluation means to delay the evaluation of an expression until it’s needed. Lazy evaluation is sometimes referred to as call-by-need.

The opposite of lazy evaluation is an eager evaluation. It’s an evaluation strategy used in most programming languages.

Lazy evaluation makes it possible to:

  • define potentially infinite data structures
  • increase performance by avoiding needless computations
  • customize iteration behavior for data structures that want its elements accessible to the public

Iterators

Iterators in JavaScript (since ECMAScript 6) are what make it possible to lazy evaluate and create user-defined data sequences.

Iteration is a mechanism for traversing data. Iterators are pointers for traversing elements of data structure, called Iterable. A pointer for producing a sequence of values.

An iterator is an object that can be iterated over. It abstracts a container of data to make it behave like an iterable object.

The iterator does not compute the value of each item when instantiated. The next value is generated only when requested. This is useful, especially for large data sets or sequences of an infinite number of elements.

Iterables

Iterables are data structures that want their elements accessible to the public.

Many APIs accept iterables, for example:

  • new Map([iterable])
  • new WeakMap([iterable])
  • new Set([iterable])
  • new WeakSet([iterable])
  • Promise.all([iterable])
  • Promise.race([iterable])
  • Array.from([iterable])

There’re also statements and expressions that expect iterables, for example:

  • for ... of (loop)
  • ... (spread operator)
  • const [a, b, ..] = iterable; (destructuring assignment)
  • yield* (generator delegation)

There’s a number of already built-in iterables in JavaScript:
String , Array , TypedArray , Map , Set.

Iteration protocols

Iterators and iterables conform to iteration protocols.

Protocol is set of interfaces and rules how to use them.

Iterators conform to the iterator protocol. Iterables conform to the iterable protocol.

The iterable protocol

Iterable protocol allows JavaScript objects to define or customize their iteration behavior.

For an object to become iterable, it must implement an iterator method accessible through Symbol.iterator . This method is a factory for iterators.

Using TypeScript the iterable protocol looks as follows:

interface Iterable {
[Symbol.iterator]() : Iterator;
}

[Symbol.iterator]() is a zero-argument function. It is invoked on the iterable object, which means you can access the iterable through this . It can be either a regular function or a generator function.

The iterator protocol

Iterator protocol defines a standard way to produce a sequence of values.

For an object to become an iterator, it must implement a next() method. Optionally the iterator can implement a return() method, we will discuss this later in this article.

Using TypeScript the iteration protocol looks as follows:

interface Iterator {
next() : IteratorResult;
return?(value?: any): IteratorResult;
}

Where IteratorResult is:

interface IteratorResult {
value?: any;
done: boolean;
}
  • done informs the consumer if the iterator has been consumed, false means there are still values to be produced, true means the iterator has reached its end
  • value can be any JavaScript value, it’s the value exposed to the consumer

When done is true value can be omitted.

Put together

To visualize the connection between iterable and iterator see the following image.

Iterable and iterator

The connection between iterable and iterator

⌨️ Showtime

Alright, enough theory. Let’s work through some examples. We will start with some basic examples and little by little add what we have learned so far to make things more interesting.

Range iterator

Let’s begin with a very basic iterator, the createRangeIterator iterator.

We’re manually calling it.next() to get the next IteratorResult. Last call returns { done: true } which means the iterator is now consumed and will not produce any more values.

Simple iterator

Iterable range iterator

Earlier in this article, I have mentioned that some statements and expressions in JavaScript expect iterables. Because of this, our previous example will not work when used, for instance, with for ... of loop.

But it’s easy enough to create an object that conforms to both iterator and iterable protocols.

To visualize this see the following image.

Iterable iterator

An object that is both iterable and iterator
Iterable iterator

Infinite sequence iterator

Iterators can express sequences of unlimited size because they compute the value only when you ask for it.

Be careful not to use spread operator (...) on infinite iterators. JavaScript will try to consume the iterator and since the iterator is infinite it will never reach its end. Instead, your app will crash because you will run out of memory.

Also the for ... of loop over such iterable would be endless. Make sure to exit the loop. Otherwise, you will also run out of memory.

Infinite iterator

Closing iterator

Earlier we mentioned iterators can optionally have a return() method. This method is used when the iterator was not iterated over until the end and lets the iterator do a cleanup.

for ... of loops can terminate the iteration earlier by:

  • break
  • continue (when you continue outer loop with label)
  • throw
  • return

The following constructs close iterators that are not consumed:

  • for ... of
  • yield*
  • destructuring
  • Array.from
  • Map(), Set(), WeakMap(), WeakSet()
  • Promise.all(), Promise.race()

Taken from https://2ality.com/2015/02/es6-iteration.html.

Iterator cleanup through return()
  • If you know that the iterator has reached its end you call the cleanup() function manually.
  • If there was an abrupt completion, the return() comes into play and does the cleanup for us.

💥 Extra

If you have made it to this point, let’s add something extra.

Combinators

Combinators are functions that combine existing iterables to create new ones. A composition of iterables.

Because of this, we are able to create a lot of utility functions. How about map or filter? See the following code and give it a minute to sink in.

Combinators

Yay! That was a lot of code. Soon we will look at how all this can be refactored using generators and functional programming concepts. You will be surprised how compact all of this code can get.

Stay safe, stay tuned, and watch out for my upcoming articles, we still have got a lot to cover.


Author: admin

Leave a Reply

Your email address will not be published.