Lazy Evaluation with Immutable.js

Since being introduced to immutable application architectures through the use of React along with learning how to build applications with its unidirectional data flow constraint it wasn’t long before I would come across persistent data structures.

I’ve been using data structures since learning my first programming language but it was only until I came into contact with the need for immutability when I learn’t that there was a distinction between persistent and non-persistent data structures. A persistent data structure conserves the previous versions of itself by yielding a new version of itself after you perform operations on it. This might seem inefficient if you’re unaware of the underlying data structures behind them as you might just assume each element is cloned leading to an O(n) operation for a shallow copy along with doubling the amount of memory required. This however is not the case and there are some really interesting optimisations utilised. A trie is one of the data structures which can be used behind an immutable associative array whereby you employ a technique named structural sharing with references. Instead of cloning each element within the structure you create a new trie and reference back to elements which have not changed in value, this does however require an environment with garbage collection.

Since promoting the use of high-order functions, of which are offered by libraries such as Immutable.js, I have had to stress the importance and difference of eager and lazy evaluation. High-order functions are great, they allow you to express operations on data structures in a generic way as opposed to re-implementing them over and over in an imperative fashion and you safe-guard yourself by knowing that the libraries/API’s offering these functions are covered by tests and you’re describing your intent of the operations in a monadic way; they can however be also assumed to be less efficient due to the possible execution strategy that being either lazy or eager. You can find yourself in a scenario where you perform some operations on a data structure and one of those can perform an eager operation which leads to more computations being performed and more memory utilised than intended, it’s important to profile your use of these operators and assert to see if it is possible to make use of lazy evaluation.

Immutable.js offers something called a ‘Seq’, this is a representation of a lazy operation allowing you to chain a number of high-order functions and only have them executed when iterating over the result. This is particularly interesting as it allows you to express an operation over a range which could exceed memory such as iterating from 0 to Infinity, yes it’s possible!

I wouldn’t eagerly evaluate this though!

You can for example declare the following seq:

import { Seq } from 'immutable'

const doublesOverFive = Seq.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
                           .filter(x => x > 5)
                           .map(x => x * 2)

Then as soon as you perform an iteration for example by using .get() or casting it into data structure the execution will be performed, this could be primarily useful on a large data set which requires transformation but not up until the point the user performs an action. For the most part though I try to ensure that the majority of my client-side applications do as little data-transformation as possible by offloading that to the back-end.

I'm a software engineer with a various range of experience with different technologies. I really enjoy functional programming and teaching others.