Lazy Transformations with Immutable.js

Immutable.js is a javascript library that provides immutable data structures in Javascript, with an intuitive and clean interface. The goal of this post is not to discuss the merits of using Immutable.js. This post will focus on describing the Seq data structure in Immutable.js. Seq is a special data structure in that it allows us to defer iteration and execution of a computation until the time it is read. This allows us to separate a computation’s description and its execution temporally.

A Common Example…

Consider the following snippet that transforms a collection; first by filtering to meet a some predicates and then by applying a transformation via map.

Immutable.List([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
  .filter(value => value < 5)
  .filter(value => value % 2 === 0)
  .map(value => value * 10);// List [20, 40]

The code above will generate a new list of values as soon as the expression is parsed. At each step the above will generate an intermediary collection that has the next action in the chain applied. If we unchain the transformation we may end up with something like below:

let fullList = Immutable.List([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]); 
let lessThan5List = fullList.filter(value => value < 5); // List [1, 2, 3, 4]
let evenLessThan5List = lessThan5List.filter(value => value % 2 === 0); // List [2, 4]
let multiples10LessThan5List =  evenLessThan5List.map(value => value * 10); // List [20, 40]

In this second example the intermediary collections are more apparent. Each subsequent collection is smaller, we are continually iterating over the same few elements. Looking at the above code, how many times does the value 2 gets inspected across all the lists? (hint: it’s more than once)

Considering the original chained version of the code there is one common argument against chaining multiple filters and maps. That argument is that, “we should reduce the number of times we iterate the collection”. And the solution comes down to implementing something as follows:

Immutable.List([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
  .reduce((newList, value) => {
    if (value >= 5) return newList;
    if (value % 2 !== 0) return newList;
    return newList.push(value * 10);
  }, Immutable.List()); // List [20, 40]

While this solution is not terrible, using a reducer has a certain amount of additional overhead. Notably the conditions for keeping values are the complement(opposite), and the transformation actions is surrounded by some noise from lower level operations(pushing to the accumulator).

I am not the biggest fan of the using the reducer to circumvent the multiple iterations. Having multiple filter and map actions describe the transformation of the collection with much less overhead to the reader. Thus we arrive at a sort of impasse where the base (List, Set, Map) collections are not enough to provide the preferred performance and expression.

Let’s be Lazy…

Seq is a lazy construct that allows us to separate the description of a computation and the execution of that computation. The code below is a description of the computation that needs to happen, not unlike the original snippet above. The collection is wrapped by Seq and it is not iterated until the it is read. The following chaining of filter and map actions each create a Seq, which can be seen as a stream of values; each value passing through each of the transformation actions at once.

let pendingSeq = Immutable.Seq([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
  .filter(value => value < 5)
  .filter(value => value % 2 === 0)
  .map(value => value * 10);

pendingSeq.get(0) // Finally Computes first value.

Seq iterates the original collection once but has the same net effect as the actions taken in List, Map, and Set which iterate the entire collection, creating intermediary collections at each step, which then get iterated again at the next step.

Below are two diagrams to help illustrate the difference in how the values are computed to compute a final list.

Seq is able to apply the filter and map operations consecutively to each value while only iterating the collection once, the way it does this is by implementing a transducer(transforming-reducer). Essentially, Seq is taking our actions and reducing the values similar to our alternate implementation with a reducer, but in a generalized way. If you are interested in learning more about transducers, check out this great article by Roman Liutikov: Understanding Transducers in Javascript.

Now we can rest assured that by using Seq we can have our expressivity and performance at the same time. However Seq do have a few gotchas that have the possibility of undoing our previous improvements.

Seq Gotchas

While Seq is a lazy data structure it is not a memoized lazy data structure. This means that every time we read a value from our sequence such as mySeq.get(10) the iteration to get to the value at index 10 from our original collection has to start over. For this reason when you are ready to start using the results of Seq, it may be best to convert back to a non-lazy data structure like a List or Map.

Immutable.js allows us to do this by invoking helper methods toList(), toMap(), toSet() and numerous others. This forces evaluation of our actions.

// See above for definition of `pendingSeq`
// Time to use our list:
let myList = pendingSeq.toList();

console.log("Top 2 Results Are:")
console.log(pendingSeq.get(0))
console.log(pendingSeq.get(1))

The snippet about would work just fine if we did not cast with toList however, every time we read a value the values leading up to the index would have to be computed also. When getting index 0 we just compute the first value. When getting index 1 Seq also has to compute index 0 again, as well as index 1, so on and so forth. This gives us an approximate complexity of O(n^2) if we iterate over the indices individually. To see this in action checkout this js bin: https://jsbin.com/qexularabe/edit?js,console.

Getting a Seq

If you are already using an the Seq data structure, Immutable provides a helper method: toSeq(). This helper yields a lazy Seq that you can use as illustrated in this post. If we return to our original snippet that showed the expressivity we desired we can see how simple it can be to use Seq to keep the expressiveness of multiple actions, and the performance of only iterating the original collection once.

Immutable.List([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
  .toSeq()
  .filter(value => value < 5)
  .filter(value => value % 2 === 0)
  .map(value => value * 10)
  .toList(); // List [20, 40]

Conclusion

Hopefully I’ve been able to make the case for using Seq in Immutable.js and given you a glimpse into the possibility for lazy data structures and transducers. May your expressions remain readable and performant.