An immutable array disguised as a regular one in Javascript

immutable-array.md

Iarray is an immutable Array that can be used like a regular Array in some cases and offers the following efficient operations for huge amounts of data:

• get/set/del an element
• unshift/shift an element (cons/uncons in FP terms)
• push/pop an element (snoc/unsnoc in FP terms)
• concatenate two Iarrays (append in FP terms)

You can use Iarray like a regular Array in the following situations:

• xs[0] (get through bracket syntax)
• Array.from or for..of (Iterable)
• const [x, ...xs] = iarray (destructuring assigment)

Please not that the rest syntax ...xs implicitly converts an Iarray back to an Array.

However, the following operations are not possible:

• xs[0] = "foo" (because statement depends on mutation)
• iarray.concat([1,2,3]) (applying Array.prototype methods)

Example

Here is a rather contrieved example that illustrates the potential of the concept:

const xs = Array(1e6).fill(1).map((x, i) => x + i),
  ys = Iarray(xs);

const arrTake = n => ([x, ...xs]) =>
  n === 0
    ? []
    : [x].concat(arrTake(n - 1) (xs));
  
const iarrTake = n => ([x, xs]) =>
  n === 0
    ? iarrEmpty
    : iarrCons(x) (iarrTake(n - 1) (iarrUncons(xs)));

iarrTake(100) (iarrUncons(ys)); // way faster
arrTake(100) (xs);

run code

Please note that I usually would wrap iarrTake in another function to abstract from the initial iarrUncons call.

Technical Background

Iarray is based on a Hashed Array Mapped Trie (HAMT) and Proxys and thus is a persistent data structure. You can find the implementation on Github

Right now the Iarray implementation is just a proof of concept.