npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

immutable-tuple

v0.4.10

Published

Immutable finite list objects with constant-time equality testing (===) and no memory leaks

Downloads

209,413

Readme

immutable-tuple Build Status

Immutable finite list objects with constant-time equality testing (===) and no memory leaks.

Installation

First install the package from npm:

npm install immutable-tuple

or clone it from GitHub and then run npm install to compile the source code:

git clone https://github.com/benjamn/immutable-tuple.git
cd immutable-tuple
npm install
npm test # if skeptical

Usage

This package exports a single function called tuple, both as a default export and as an equivalent named export, so all of the following import styles will work:

import tuple from "immutable-tuple";
import { tuple } from "immutable-tuple";
const { tuple } = require("immutable-tuple");
const tuple = require("immutable-tuple").tuple;

Constructing tuples

The tuple function takes any number of arguments and returns a unique, immutable object that inherits from tuple.prototype and is guaranteed to be === any other tuple object created from the same sequence of arguments:

import assert from "assert";

const obj = { asdf: 1234 };
const t1 = tuple(1, "asdf", obj);
const t2 = tuple(1, "asdf", obj);

assert.strictEqual(t1 === t2, true);
assert.strictEqual(t1, t2);

Although the tuple function can be invoked using new tuple(...) syntax, using new is not recommended, since the new object will simply be thrown away.

Own tuple properties

The tuple object has a fixed numeric length property, and its elements may be accessed using array index notation:

assert.strictEqual(t1.length, 3);

t1.forEach((x, i) => {
  assert.strictEqual(x, t2[i]);
});

Nested tuples

Since tuple objects are just another kind of JavaScript object, naturally tuples can contain other tuples:

assert.strictEqual(
  tuple(t1, t2),
  tuple(t2, t1)
);

assert.strictEqual(
  tuple(1, t2, 3)[1][2],
  obj
);

However, because tuples are immutable and always distinct from any of their arguments, it is not possible for a tuple to contain itself, nor to contain another tuple that contains the original tuple, and so forth.

Constant time === equality

Since tuple objects are identical when (and only when) their elements are identical, any two tuples can be compared for equality in constant time, regardless of how many elements they contain.

This behavior also makes tuple objects useful as keys in a Map, or elements in a Set, without any extra hashing or equality logic:

const map = new Map;

map.set(tuple(1, 12, 3), {
  author: tuple("Ben", "Newman"),
  releaseDate: Date.now()
});

const version = "1.12.3";
const info = map.get(tuple(...version.split(".").map(Number)));
if (info) {
  console.log(info.author[1]); // "Newman"
}

Array methods

Every non-destructive method of Array.prototype is supported by tuple.prototype, including sort and reverse, which return a modified copy of the tuple without altering the original:

assert.strictEqual(
  tuple("a", "b", "c").slice(1, -1),
  tuple("b")
);

assert.strictEqual(
  tuple(6, 2, 8, 1, 3, 0).sort(),
  tuple(0, 1, 2, 3, 6, 8)
);

assert.strictEqual(
  tuple(1).concat(2, tuple(3, 4), 5),
  tuple(1, 2, 3, 4, 5)
);

Shallow immutability

While the identity, number, and order of elements in a tuple is fixed, please note that the contents of the individual elements are not frozen in any way:

const obj = { asdf: 1234 };
tuple(1, "asdf", obj)[2].asdf = "oyez";
assert.strictEqual(obj.asdf, "oyez");

Iterability

Every tuple object is array-like and iterable, so ... spreading and destructuring work as they should:

func(...tuple(a, b));
func.apply(this, tuple(c, d, e));

assert.deepEqual(
  [1, ...tuple(2, 3), 4],
  [1, 2, 3, 4]
);

assert.strictEqual(
  tuple(1, ...tuple(2, 3), 4),
  tuple(1, 2, 3, 4)
);

const [a, [_, b]] = tuple(1, tuple(2, 3), 4);
assert.strictEqual(a, 1);
assert.strictEqual(b, 3);

tuple.isTuple(value)

Since the immutable-tuple package could be installed multiple times in an application, there is no guarantee that the tuple constructor or tuple.prototype will be unique, so value instanceof tuple is unreliable. Instead, to test if a value is a tuple, you should use tuple.isTuple(value).

Fortunately, even if your application uses multiple different tuple constructors from different copies of this library, the resulting tuple instances will still be === each other when their elements are the same. This is especially convenient given that this library provides both a CommonJS bundle and an ECMAScript module bundle, and some module systems might accidentally load those bundles simultaneously.

Implementation details

Thanks to Docco, you can read my implementation comments side-by-side with the actual code by visiting the GitHub pages site for this repository.

Instance pooling (internalization)

Any data structure that guarantees === equality based on structural equality must maintain some sort of internal pool of previously encountered instances.

Implementing such a pool for tuples is fairly straightforward (though feel free to give it some thought before reading this code, if you like figuring things out for yourself):

const pool = new Map;

function tuple(...items) {
  let node = pool; 

  items.forEach(item => {
    let child = node.get(item);
    if (!child) node.set(item, child = new Map);
    node = child;
  });

  // If we've created a tuple instance for this sequence of elements before,
  // return that instance again. Otherwise create a new immutable tuple instance
  // with the same (frozen) elements as the items array.
  return node.tuple || (node.tuple = Object.create(
    tuple.prototype,
    Object.getOwnPropertyDescriptors(Object.freeze(items))
  ));
}

This implementation is pretty good, because it requires only linear time (O(items.length)) to determine if a tuple has been created previously for the given items, and you can't do better than linear time (asymptotically speaking) because you have to look at all the items.

This code is also useful as an illustration of exactly how the tuple constructor behaves, in case you weren't satisfied by my examples in the previous section.

Garbage collection

The simple implementation above has a serious problem: in a garbage-collected language like JavaScript, the pool itself will retain references to all tuple objects ever created, which prevents tuple objects and their elements (which may be very large objects) from ever being reclaimed by the garbage collector, even after they become unreachable by any other means. In other words, storing objects in this kind of tuple would inevitably cause memory leaks.

To solve this problem, it's tempting to try changing Map to WeakMap here:

const pool = new WeakMap;

and here:

if (!child) node.set(item, child = new WeakMap);

This approach is appealing because a WeakMap should allow its keys to be reclaimed by the garbage collector. That's the whole point of a WeakMap, after all. Once a tuple becomes unreachable because the program has stopped using it anywhere else, its elements are free to disappear from the pool of WeakMaps whenever they too become unreachable. In other words, something like a WeakMap is exactly what we need here.

Unfortunately, this strategy stumbles because a tuple can contain primitive values as well as object references, whereas a WeakMap only allows keys that are object references. In other words, node.set(item, ...) would fail whenever item is not an object, if node is a WeakMap. To see how the immutable-tuple library gets around this WeakMap limitation, have a look at this module.

Astute readers may object that some bookkeeping data remains in memory when you create tuple objects with prefixes of primitive values, but the important thing is that no user-defined objects are kept alive by the pool. That said, if you have any ideas for reclaiming chains of ._strongMap data, please open an issue or submit a pull request!