Immutable collections for JavaScript

 Chat on slack

Read the docs and eat your vegetables.

Docs are automatically generated from [README.md][] and [immutable.d.ts][].
Please contribute! Also, don't miss the [wiki][] which contains articles on
additional specific topics. Can't find something? Open an [issue][].

Table of contents:

- Introduction
- Getting started
- The case for Immutability
- JavaScript-first API
- Nested Structures
- Equality treats Collections as Values
- Batching Mutations
- Lazy Seq
- Additional Tools and Resources
- Contributing

Introduction

[Immutable][] data cannot be changed once created, leading to much simpler
application development, no defensive copying, and enabling advanced memoization
and change detection techniques with simple logic. [Persistent][] data presents
a mutative API which does not update the data in-place, but instead always
yields new updated data.

Immutable.js provides many Persistent Immutable data structures including:
List, Stack, Map, OrderedMap, Set, OrderedSet and Record.

These data structures are highly efficient on modern JavaScript VMs by using
structural sharing via [hash maps tries][] and [vector tries][] as popularized
by Clojure and Scala, minimizing the need to copy or cache data.

Immutable.js also provides a lazy Seq, allowing efficient
chaining of collection methods like map and filter without creating
intermediate representations. Create some Seq with Range and Repeat.

Want to hear more? Watch the presentation about Immutable.js:


[readme.md]: https://github.com/immutable-js/immutable-js/blob/main/README.md
[immutable.d.ts]: https://github.com/immutable-js/immutable-js/blob/main/type-definitions/immutable.d.ts
[wiki]: https://github.com/immutable-js/immutable-js/wiki
[issue]: https://github.com/immutable-js/immutable-js/issues
[persistent]: https://en.wikipedia.org/wiki/Persistent_data_structure
[immutable]: https://en.wikipedia.org/wiki/Immutable_object
[hash maps tries]: https://en.wikipedia.org/wiki/Hash_array_mapped_trie
[vector tries]: https://hypirion.com/musings/understanding-persistent-vector-pt-1

Getting started

Install immutable using npm.

``shell
npm install immutable
`

Or install using yarn.

`shell
yarn add immutable
`

Then require it into any module.

`js
const { Map } = require('immutable');
const map1 = Map({ a: 1, b: 2, c: 3 });
const map2 = map1.set('b', 50);
map1.get('b') + ' vs. ' + map2.get('b'); // 2 vs. 50
`

$3

Immutable.js has no dependencies, which makes it predictable to include in a Browser.

It's highly recommended to use a module bundler like webpack,
rollup, or
browserify. The immutable npm module works
without any additional consideration. All examples throughout the documentation
will assume use of this kind of tool.

Alternatively, Immutable.js may be directly included as a script tag. Download
or link to a CDN such as CDNJS
or jsDelivr.

Use a script tag to directly add Immutable to the global scope:

`html


`

Or use an AMD-style loader (such as RequireJS):

`js
require(['./immutable.min.js'], function (Immutable) {
var map1 = Immutable.Map({ a: 1, b: 2, c: 3 });
var map2 = map1.set('b', 50);
map1.get('b'); // 2
map2.get('b'); // 50
});
`

$3

Use these Immutable collections and sequences as you would use native
collections in your Flowtype or TypeScript programs while still taking
advantage of type generics, error detection, and auto-complete in your IDE.

Installing immutable via npm brings with it type definitions for Flow (v0.55.0 or higher)
and TypeScript (v2.1.0 or higher), so you shouldn't need to do anything at all!

#### Using TypeScript with Immutable.js v4

Immutable.js type definitions embrace ES2015. While Immutable.js itself supports
legacy browsers and environments, its type definitions require TypeScript's 2015
lib. Include either "target": "es2015" or "lib": "es2015" in your
tsconfig.json, or provide --target es2015 or --lib es2015 to the
tsc command.

`js
const { Map } = require('immutable');
const map1 = Map({ a: 1, b: 2, c: 3 });
const map2 = map1.set('b', 50);
map1.get('b') + ' vs. ' + map2.get('b'); // 2 vs. 50
`

#### Using TypeScript with Immutable.js v3 and earlier:

Previous versions of Immutable.js include a reference file which you can include
via relative path to the type definitions at the top of your file.

`js
///
import Immutable from 'immutable';
var map1: Immutable.Map;
map1 = Immutable.Map({ a: 1, b: 2, c: 3 });
var map2 = map1.set('b', 50);
map1.get('b'); // 2
map2.get('b'); // 50
`

The case for Immutability

Much of what makes application development difficult is tracking mutation and
maintaining state. Developing with immutable data encourages you to think
differently about how data flows through your application.

Subscribing to data events throughout your application creates a huge overhead of
book-keeping which can hurt performance, sometimes dramatically, and creates
opportunities for areas of your application to get out of sync with each other
due to easy to make programmer error. Since immutable data never changes,
subscribing to changes throughout the model is a dead-end and new data can only
ever be passed from above.

This model of data flow aligns well with the architecture of [React][]
and especially well with an application designed using the ideas of [Flux][].

When data is passed from above rather than being subscribed to, and you're only
interested in doing work when something has changed, you can use equality.

Immutable collections should be treated as _values_ rather than _objects_. While
objects represent some thing which could change over time, a value represents
the state of that thing at a particular instance of time. This principle is most
important to understanding the appropriate use of immutable data. In order to
treat Immutable.js collections as values, it's important to use the
Immutable.is() function or .equals() method to determine _value equality_
instead of the === operator which determines object _reference identity_.

`js
const { Map } = require('immutable');
const map1 = Map({ a: 1, b: 2, c: 3 });
const map2 = Map({ a: 1, b: 2, c: 3 });
map1.equals(map2); // true
map1 === map2; // false
`

Note: As a performance optimization Immutable.js attempts to return the existing
collection when an operation would result in an identical collection, allowing
for using === reference equality to determine if something definitely has not
changed. This can be extremely useful when used within a memoization function
which would prefer to re-run the function if a deeper equality check could
potentially be more costly. The === equality check is also used internally by
Immutable.is and .equals() as a performance optimization.

`js
const { Map } = require('immutable');
const map1 = Map({ a: 1, b: 2, c: 3 });
const map2 = map1.set('b', 2); // Set to same value
map1 === map2; // true
`

If an object is immutable, it can be "copied" simply by making another reference
to it instead of copying the entire object. Because a reference is much smaller
than the object itself, this results in memory savings and a potential boost in
execution speed for programs which rely on copies (such as an undo-stack).

`js
const { Map } = require('immutable');
const map = Map({ a: 1, b: 2, c: 3 });
const mapCopy = map; // Look, "copies" are free!
`

[react]: https://reactjs.org/
[flux]: https://facebook.github.io/flux/docs/in-depth-overview/

JavaScript-first API

While Immutable.js is inspired by Clojure, Scala, Haskell and other functional
programming environments, it's designed to bring these powerful concepts to
JavaScript, and therefore has an Object-Oriented API that closely mirrors that
of [ES2015][] [Array][], [Map][], and [Set][].

[es2015]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/New_in_JavaScript/ECMAScript_6_support_in_Mozilla
[array]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array
[map]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map
[set]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set

The difference for the immutable collections is that methods which would mutate
the collection, like push, set, unshift or splice, instead return a new
immutable collection. Methods which return new arrays, like slice or concat,
instead return new immutable collections.

`js
const { List } = require('immutable');
const list1 = List([1, 2]);
const list2 = list1.push(3, 4, 5);
const list3 = list2.unshift(0);
const list4 = list1.concat(list2, list3);
assert.equal(list1.size, 2);
assert.equal(list2.size, 5);
assert.equal(list3.size, 6);
assert.equal(list4.size, 13);
assert.equal(list4.get(0), 1);
`

Almost all of the methods on [Array][] will be found in similar form on
Immutable.List, those of [Map][] found on Immutable.Map, and those of [Set][]
found on Immutable.Set, including collection operations like forEach()
and map().

`js
const { Map } = require('immutable');
const alpha = Map({ a: 1, b: 2, c: 3, d: 4 });
alpha.map((v, k) => k.toUpperCase()).join();
// 'A,B,C,D'
`

$3

Designed to inter-operate with your existing JavaScript, Immutable.js
accepts plain JavaScript Arrays and Objects anywhere a method expects a
Collection.

`js
const { Map, List } = require('immutable');
const map1 = Map({ a: 1, b: 2, c: 3, d: 4 });
const map2 = Map({ c: 10, a: 20, t: 30 });
const obj = { d: 100, o: 200, g: 300 };
const map3 = map1.merge(map2, obj);
// Map { a: 20, b: 2, c: 10, d: 100, t: 30, o: 200, g: 300 }
const list1 = List([1, 2, 3]);
const list2 = List([4, 5, 6]);
const array = [7, 8, 9];
const list3 = list1.concat(list2, array);
// List [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
`

This is possible because Immutable.js can treat any JavaScript Array or Object
as a Collection. You can take advantage of this in order to get sophisticated
collection methods on JavaScript Objects, which otherwise have a very sparse
native API. Because Seq evaluates lazily and does not cache intermediate
results, these operations can be extremely efficient.

`js
const { Seq } = require('immutable');
const myObject = { a: 1, b: 2, c: 3 };
Seq(myObject)
.map(x => x * x)
.toObject();
// { a: 1, b: 4, c: 9 }
`

Keep in mind, when using JS objects to construct Immutable Maps, that
JavaScript Object properties are always strings, even if written in a quote-less
shorthand, while Immutable Maps accept keys of any type.

`js
const { fromJS } = require('immutable');

const obj = { 1: 'one' };
console.log(Object.keys(obj)); // [ "1" ]
console.log(obj['1'], obj[1]); // "one", "one"

const map = fromJS(obj);
console.log(map.get('1'), map.get(1)); // "one", undefined
`

Property access for JavaScript Objects first converts the key to a string, but
since Immutable Map keys can be of any type the argument to get() is
not altered.

$3

All Immutable.js Collections can be converted to plain JavaScript Arrays and
Objects shallowly with toArray() and toObject() or deeply with toJS().
All Immutable Collections also implement toJSON() allowing them to be passed
to JSON.stringify directly. They also respect the custom toJSON() methods of
nested objects.

`js
const { Map, List } = require('immutable');
const deep = Map({ a: 1, b: 2, c: List([3, 4, 5]) });
console.log(deep.toObject()); // { a: 1, b: 2, c: List [ 3, 4, 5 ] }
console.log(deep.toArray()); // [ 1, 2, List [ 3, 4, 5 ] ]
console.log(deep.toJS()); // { a: 1, b: 2, c: [ 3, 4, 5 ] }
JSON.stringify(deep); // '{"a":1,"b":2,"c":[3,4,5]}'
`

$3

Immutable.js supports all JavaScript environments, including legacy
browsers (even IE11). However it also takes advantage of features added to
JavaScript in [ES2015][], the latest standard version of JavaScript, including
[Iterators][], [Arrow Functions][], [Classes][], and [Modules][]. It's inspired
by the native [Map][] and [Set][] collections added to ES2015.

All examples in the Documentation are presented in ES2015. To run in all
browsers, they need to be translated to ES5.

`js
// ES2015
const mapped = foo.map(x => x * x);
// ES5
var mapped = foo.map(function (x) {
return x * x;
});
`

All Immutable.js collections are [Iterable][iterators], which allows them to be
used anywhere an Iterable is expected, such as when spreading into an Array.

`js
const { List } = require('immutable');
const aList = List([1, 2, 3]);
const anArray = [0, ...aList, 4, 5]; // [ 0, 1, 2, 3, 4, 5 ]
`

Note: A Collection is always iterated in the same order, however that order may
not always be well defined, as is the case for the Map and Set.

[iterators]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/The_Iterator_protocol
[arrow functions]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Functions/Arrow_functions
[classes]: https://wiki.ecmascript.org/doku.php?id=strawman:maximally_minimal_classes
[modules]: https://www.2ality.com/2014/09/es6-modules-final.html

Nested Structures

The collections in Immutable.js are intended to be nested, allowing for deep
trees of data, similar to JSON.

`js
const { fromJS } = require('immutable');
const nested = fromJS({ a: { b: { c: [3, 4, 5] } } });
// Map { a: Map { b: Map { c: List [ 3, 4, 5 ] } } }
`

A few power-tools allow for reading and operating on nested data. The
most useful are mergeDeep, getIn, setIn, and updateIn, found on List,
Map and OrderedMap.

`js
const { fromJS } = require('immutable');
const nested = fromJS({ a: { b: { c: [3, 4, 5] } } });

const nested2 = nested.mergeDeep({ a: { b: { d: 6 } } });
// Map { a: Map { b: Map { c: List [ 3, 4, 5 ], d: 6 } } }

console.log(nested2.getIn(['a', 'b', 'd'])); // 6

const nested3 = nested2.updateIn(['a', 'b', 'd'], value => value + 1);
console.log(nested3);
// Map { a: Map { b: Map { c: List [ 3, 4, 5 ], d: 7 } } }

const nested4 = nested3.updateIn(['a', 'b', 'c'], list => list.push(6));
// Map { a: Map { b: Map { c: List [ 3, 4, 5, 6 ], d: 7 } } }
`

Equality treats Collections as Values

Immutable.js collections are treated as pure data _values_. Two immutable
collections are considered _value equal_ (via .equals() or is()) if they
represent the same collection of values. This differs from JavaScript's typical
_reference equal_ (via === or ==) for Objects and Arrays which only
determines if two variables represent references to the same object instance.

Consider the example below where two identical Map instances are not
_reference equal_ but are _value equal_.

`js
// First consider:
const obj1 = { a: 1, b: 2, c: 3 };
const obj2 = { a: 1, b: 2, c: 3 };
obj1 !== obj2; // two different instances are always not equal with ===

const { Map, is } = require('immutable');
const map1 = Map({ a: 1, b: 2, c: 3 });
const map2 = Map({ a: 1, b: 2, c: 3 });
map1 !== map2; // two different instances are not reference-equal
map1.equals(map2); // but are value-equal if they have the same values
is(map1, map2); // alternatively can use the is() function
`

Value equality allows Immutable.js collections to be used as keys in Maps or
values in Sets, and retrieved with different but equivalent collections:

`js
const { Map, Set } = require('immutable');
const map1 = Map({ a: 1, b: 2, c: 3 });
const map2 = Map({ a: 1, b: 2, c: 3 });
const set = Set().add(map1);
set.has(map2); // true because these are value-equal
`

Note: is() uses the same measure of equality as [Object.is][] for scalar
strings and numbers, but uses value equality for Immutable collections,
determining if both are immutable and all keys and values are equal
using the same measure of equality.

[object.is]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/is

#### Performance tradeoffs

While value equality is useful in many circumstances, it has different
performance characteristics than reference equality. Understanding these
tradeoffs may help you decide which to use in each case, especially when used
to memoize some operation.

When comparing two collections, value equality may require considering every
item in each collection, on an O(N) time complexity. For large collections of
values, this could become a costly operation. Though if the two are not equal
and hardly similar, the inequality is determined very quickly. In contrast, when
comparing two collections with reference equality, only the initial references
to memory need to be compared which is not based on the size of the collections,
which has an O(1) time complexity. Checking reference equality is always very
fast, however just because two collections are not reference-equal does not rule
out the possibility that they may be value-equal.

#### Return self on no-op optimization

When possible, Immutable.js avoids creating new objects for updates where no
change in _value_ occurred, to allow for efficient _reference equality_ checking
to quickly determine if no change occurred.

`js
const { Map } = require('immutable');
const originalMap = Map({ a: 1, b: 2, c: 3 });
const updatedMap = originalMap.set('b', 2);
updatedMap === originalMap; // No-op .set() returned the original reference.
`

However updates which do result in a change will return a new reference. Each
of these operations occur independently, so two similar updates will not return
the same reference:

`js
const { Map } = require('immutable');
const originalMap = Map({ a: 1, b: 2, c: 3 });
const updatedMap = originalMap.set('b', 1000);
// New instance, leaving the original immutable.
updatedMap !== originalMap;
const anotherUpdatedMap = originalMap.set('b', 1000);
// Despite both the results of the same operation, each created a new reference.
anotherUpdatedMap !== updatedMap;
// However the two are value equal.
anotherUpdatedMap.equals(updatedMap);
`

Batching Mutations

> If a tree falls in the woods, does it make a sound?
>
> If a pure function mutates some local data in order to produce an immutable
> return value, is that ok?
>
> — Rich Hickey, Clojure

Applying a mutation to create a new immutable object results in some overhead,
which can add up to a minor performance penalty. If you need to apply a series
of mutations locally before returning, Immutable.js gives you the ability to
create a temporary mutable (transient) copy of a collection and apply a batch of
mutations in a performant manner by using withMutations. In fact, this is
exactly how Immutable.js applies complex mutations itself.

As an example, building list2 results in the creation of 1, not 3, new
immutable Lists.

`js
const { List } = require('immutable');
const list1 = List([1, 2, 3]);
const list2 = list1.withMutations(function (list) {
list.push(4).push(5).push(6);
});
assert.equal(list1.size, 3);
assert.equal(list2.size, 6);
`

Note: Immutable.js also provides asMutable and asImmutable, but only
encourages their use when withMutations will not suffice. Use caution to not
return a mutable copy, which could result in undesired behavior.

_Important!_: Only a select few methods can be used in withMutations including
set, push and pop. These methods can be applied directly against a
persistent data-structure where other methods like map, filter, sort,
and splice will always return new immutable data-structures and never mutate
a mutable collection.

Lazy Seq

Seq describes a lazy operation, allowing them to efficiently chain
use of all the higher-order collection methods (such as map and filter)
by not creating intermediate collections.

Seq is immutable — Once a Seq is created, it cannot be
changed, appended to, rearranged or otherwise modified. Instead, any mutative
method called on a Seq will return a new Seq.

Seq is lazy — Seq does as little work as necessary to respond to any
method call. Values are often created during iteration, including implicit
iteration when reducing or converting to a concrete data structure such as
a List or JavaScript Array.

For example, the following performs no work, because the resulting
Seq's values are never iterated:

`js
const { Seq } = require('immutable');
const oddSquares = Seq([1, 2, 3, 4, 5, 6, 7, 8])
.filter(x => x % 2 !== 0)
.map(x => x * x);
`

Once the Seq is used, it performs only the work necessary. In this
example, no intermediate arrays are ever created, filter is called three
times, and map is only called once:

`js
oddSquares.get(1); // 9
`

Any collection can be converted to a lazy Seq with Seq().

`js
const { Map, Seq } = require('immutable');
const map = Map({ a: 1, b: 2, c: 3 });
const lazySeq = Seq(map);
`

Seq allows for the efficient chaining of operations, allowing for the
expression of logic that can otherwise be very tedious:

`js
lazySeq
.flip()
.map(key => key.toUpperCase())
.flip();
// Seq { A: 1, B: 2, C: 3 }
`

As well as expressing logic that would otherwise seem memory or time
limited, for example Range is a special kind of Lazy sequence.

`js
const { Range } = require('immutable');
Range(1, Infinity)
.skip(1000)
.map(n => -n)
.filter(n => n % 2 === 0)
.take(2)
.reduce((r, n) => r * n, 1);
// 1006008
`

SortedSet

See more details on SortedSet page.

SortedSet is a type of Set that keeps its values sorted by a comparator. The current implementation is using a classic B-Tree memory structure with O(N) space requirements and O(log N) get, add, and delete operations.

Example:

`js
> const { SortedSet } = require('immutable-sorted');

> const set1=SortedSet(['orange', 'apple', 'banana']);
SortedSet { "apple", "banana", "orange" }

> const set2=set1.add('mango');
SortedSet { "apple", "banana", "mango", "orange" }

> const set3=set2.delete('banana');
SortedSet { "apple", "mango", "orange" }
`

Using a custom comparator:

`js
> const reverseCmp=(a,b)=>(a>b?-1:a

> const set4=SortedSet(set1, reverseCmp);
SortedSet { "orange", "banana", "apple" }

> const set5=set4.add('mango');
SortedSet { "orange", "mango", "banana", "apple" }

> const set6=set5.delete('banana');
SortedSet { "orange", "mango", "apple" }
`

Set values, like Map keys, may be of any type. Equality is determined by comparator returning 0 value. In case of a custom comparator the equality may be redefined to have a different meaning than Immutable.is.

Searching SortedSet

Many real applications require ability to efficiently search in a sorted dataset. The method:

`js
from(value, backwards);
`

returns a sequence that represents a subset of a sorted set starting with value
up to the last element in the set.

If the optional parameter backwards is set to true, the returned sequence will
list the entries backwards, starting with value down to the first element in the set.

Example:

`js
const { SortedSet } = require('immutable-sorted');

const abc = SortedSet(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"]);

> abc.from("R");
Seq { "R", "S", "T", "U", "V", "W", "X", "Y", "Z" }

> abc.from("R", true);
Seq { "R", "Q", "P", "O", "N", "M", "L", "K", "J", "I", "H", "G", "F", "E", "D", "C", "B", "A" }
`

The method from() can be efficiently combined with take() to retrieve the desired number of values or with takeWhile() to retrieve a specific range:

`js
> abc.from("R").take(5);
Seq { "R", "S", "T", "U", "V" }

> abc.from("R").takeWhile(s => s < "W");
Seq { "R", "S", "T", "U", "V" }

> abc.from("R", true).take(5);
Seq { "R", "Q", "P", "O", "N" }

> abc.from("R", true).takeWhile(s => s > "K");
Seq { "R", "Q", "P", "O", "N", "M", "L" }
`

We can also use the numeric index to efficiently iterate through the sorted collections starting from numeric index as if they were arrays. The method:

`js
fromIndex(n, backwards);
`

is optimized to quickly find the n-th entry inside the b-tree structure by checking the computed sizes of underlying nodes. Even though the algorithm is not as fast as working with native array, it is faster by orders of magnitude than walking through the first n elements in unindexed collection to skip them. The access time is O(log N).

Examples:

`js
> abc.fromIndex(4).take(5);
Seq { "E", "F", "G", "H", "I" }

> abc.fromIndex(4, true).take(5);
Seq { "E", "D", "C", "B", "A" }
`

Working with objects

Many real use cases will be about storing the whole objects in SortedSet. That will usually be meaningful only when custom comparator is defined.

Let's consider the following example with city objects:

`js
> const { SortedSet, Seq, fromJS } = require('immutable-sorted');

// Have an array of city objects
> const cities=[
{state: 'MA', city: 'Boston'},
{city: 'Miami', state: 'FL'},
{city: 'Seattle', state: 'WA'},
{city: 'Phoenix', state: 'AZ'}];

// Make a seq that converts cities from JS into immutable objects
> const citiesSeq=Seq(cities).map((v)=>fromJS(v));

// Create a default SortedSet
> const set1=SortedSet(citiesSeq);
SortedSet {
Map { "city": "Miami", "state": "FL" },
Map { "city": "Phoenix", "state": "AZ" },
Map { "city": "Seattle", "state": "WA" },
Map { "state": "MA", "city": "Boston" } }
`

When relying on defaultComparator, like in example above, the objects get sorted by their string representations from toString() method. This is usually not what the application designers want. In our case it makes more sense to sort by the city name, than the whole string representation.

Let's create a custom comparator:

`js
// Define a general comparator
> const cmp=(a,b)=>(a>b?1:(a

// Define a comparator of city names
> let citiesCmp=(a,b)=>cmp(a.get('city'), b.get('city'));

// Create a SortedSet with custom comparator
> const set2=SortedSet(citiesSeq, citiesCmp);
SortedSet {
Map { "state": "MA", "city": "Boston" },
Map { "city": "Miami", "state": "FL" },
Map { "city": "Phoenix", "state": "AZ" },
Map { "city": "Seattle", "state": "WA" } }
`

The custom comparator that we have created seems to work as expected. Now let's add into the collection another city of Phoenix, this time from state Illinois.

`js
> const set3=set2.add(fromJS({city: 'Phoenix', state: 'IL'}));
SortedSet {
Map { "state": "MA", "city": "Boston" },
Map { "city": "Miami", "state": "FL" },
Map { "city": "Phoenix", "state": "IL" },
Map { "city": "Seattle", "state": "WA" } }
`

The Phoenix, AZ had been replaced with Phoenix, IL. This is because of the way the custom comparator is defined. It determines equality by comparing city names only, therefore Phoenix, AZ and Phoenix, IL are equal according to this comparator. Let's try to extend the comparator to compare the city name first and if they match then determine the result by comparing the state.

`js
// Define more complex custom comparator
> citiesCmp=(a,b)=>cmp(a.get('city'), b.get('city'))||cmp(a.get('state'), b.get('state'));

// Create a new SortedSet with new custom comparator
> const set4=SortedSet(set2, citiesCmp);
SortedSet {
Map { "state": "MA", "city": "Boston" },
Map { "city": "Miami", "state": "FL" },
Map { "city": "Phoenix", "state": "AZ" },
Map { "city": "Seattle", "state": "WA" } }

// set4 looks the same as set2, now let's add the conflicting Phoenix, IL to set4
> const set5=set4.add(fromJS({city: 'Phoenix', state: 'IL'}));
SortedSet {
Map { "state": "MA", "city": "Boston" },
Map { "city": "Miami", "state": "FL" },
Map { "city": "Phoenix", "state": "AZ" },
Map { "city": "Phoenix", "state": "IL" },
Map { "city": "Seattle", "state": "WA" } }
`

The custom comparator behaves as expected. Now let's swap the order of commands in the comparator and sort by state first and by city name second.

`js
> const stateCitiesCmp=(a,b)=>cmp(a.get('state'), b.get('state'))||cmp(a.get('city'), b.get('city'));

> const set6=SortedSet(set5, stateCitiesCmp);
SortedSet {
Map { "city": "Phoenix", "state": "AZ" },
Map { "city": "Miami", "state": "FL" },
Map { "city": "Phoenix", "state": "IL" },
Map { "state": "MA", "city": "Boston" },
Map { "city": "Seattle", "state": "WA" } }
`

SortedMap

See more details on SortedMap page.

SortedMap is a type of Map that keeps its entries (their keys) sorted by a comparator. The current implementation is using a classic B-Tree memory structure with O(N) space requirements and O(log N) get, set, and delete operations.

Example:

`js
const { SortedMap } = require('immutable-sorted');

> const map1=SortedMap([['orange','orange'], ['apple','red'], ['banana','yellow']]);
SortedMap { "apple": "red", "banana": "yellow", "orange": "orange" }

> const map2=map1.set('mango', 'yellow/orange');
SortedMap { "apple": "red", "banana": "yellow", "mango": "yellow/orange", "orange": "orange" }

> const map3=map2.delete('banana');
SortedMap { "apple": "red", "mango": "yellow/orange", "orange": "orange" }
`

Using a custom comparator:

`js
> const reverseCmp=(a,b)=>(a>b?-1:(a

> const map4=SortedMap(map1, reverseCmp);
SortedMap { "orange": "orange", "banana": "yellow", "apple": "red" }

> const map5=map4.set('mango', 'yellow/orange');
SortedMap { "orange": "orange", "mango": "yellow/orange", "banana": "yellow", "apple": "red" }

> const map6=map5.delete('banana');
SortedMap { "orange": "orange", "mango": "yellow/orange", "apple": "red" }
`

When iterating a SortedMap, the order of entries is guaranteed to be the same as the sorted order of keys determined by a comparator.

Map keys and values may be of any type. Equality of keys is determined by comparator returning 0 value. In case of a custom comparator the equality may be redefined to have a different meaning than Immutable.is.

Searching SortedMap

Many real applications require ability to efficiently search in a sorted data structure. The method:

`js
from(key, backwards);
`

returns a sequence that represents a portion of this sorted map starting with a specific key up to the last entry in the sorted map.

If the optional parameter backwards is set to true, the returned sequence will list the entries backwards, starting with key down to the first entry in the sorted map.

Example:

`js
> const abc = SortedMap([["A", "a"], ["B", "b"], ["C", "c"], ["D", "d"], ["E", "e"], ["F", "f"], ["G", "g"], ["H", "h"], ["I", "i"], ["J", "j"], ["K", "k"], ["L", "l"], ["M", "m"], ["N", "n"], ["O", "o"], ["P", "p"], ["Q", "q"], ["R", "r"], ["S", "s"], ["T", "t"], ["U", "u"], ["V", "v"], ["W", "w"], ["X", "x"], ["Y", "y"], ["Z", "z"]]);

> abc.from("R");
Seq { "R": "r", "S": "s", "T": "t", "U": "u", "V": "v", "W": "w", "X": "x", "Y": "y", "Z": "z" }

> abc.from("R", true);
Seq { "R": "r", "Q": "q", "P": "p", "O": "o", "N": "n", "M": "m", "L": "l", "K": "k", "J": "j", "I": "i", "H": "h", "G": "g", "F": "f", "E": "e", "D": "d", "C": "c", "B": "b", "A": "a" }
`

The method from() can be efficiently combined with take() to retrieve the desired number of values or with takeWhile() to retrieve a specific range:

`js
> abc.from("R").take(5);
Seq { "R": "r", "S": "s", "T": "t", "U": "u", "V": "v" }

> abc.from("R").takeWhile((v, k) => k < "W");
Seq { "R": "r", "S": "s", "T": "t", "U": "u", "V": "v" }

> abc.from("R", true).take(5);
Seq { "R": "r", "Q": "q", "P": "p", "O": "o", "N": "n" }

> abc.from("R", true).takeWhile((v, k) => k > "K");
Seq { "R": "r", "Q": "q", "P": "p", "O": "o", "N": "n", "M": "m", "L": "l" }
`

Working with objects

Many real use cases will be about storing the whole objects in SortedMap. That will usually be meaningful only when custom comparator is defined.

Let's consider the following example with city objects as keys and their co-ordinates as values:

`js
> const { SortedMap, Seq, fromJS } = require('immutable-sorted');

// Have an array of city objects
> const cities=[
[{state: 'MA', city: 'Boston'}, ['42°21′N','71°04′W']],
[{city: 'Miami', state: 'FL'},['25°47′N','80°13′W']],
[{city: 'Seattle', state: 'WA'},['47°37′N','122°20′W']],
[{city: 'Phoenix', state: 'AZ'},['33°27′N','112°04′W']]];

// Make a seq that converts cities and their co-ordinates from JS into immutable objects
> const citiesSeq=Seq.Keyed(cities).mapKeys((v)=>fromJS(v)).map((v)=>fromJS(v));
Seq {
Map { "state": "MA", "city": "Boston" }: List [ "42°21′N", "71°04′W" ],
Map { "city": "Miami", "state": "FL" }: List [ "25°47′N", "80°13′W" ],
Map { "city": "Seattle", "state": "WA" }: List [ "47°37′N", "122°20′W" ],
Map { "city": "Phoenix", "state": "AZ" }: List [ "33°27′N", "112°04′W" ] }

// Create a default SortedMap
> const map1=SortedMap(citiesSeq);
SortedMap {
Map { "city": "Miami", "state": "FL" }: List [ "25°47′N", "80°13′W" ],
Map { "city": "Phoenix", "state": "AZ" }: List [ "33°27′N", "112°04′W" ],
Map { "city": "Seattle", "state": "WA" }: List [ "47°37′N", "122°20′W" ],
Map { "state": "MA", "city": "Boston" }: List [ "42°21′N", "71°04′W" ] }
`

When relying on defaultComparator, like in example above, the objects get sorted by their string representations from toString() method. This is usually not what the application designers want. In our case it makes more sense to sort by the city name, than the whole string representation.

Let's create a custom comparator:

`js
// Define a general simple comparator
> const cmp=(a,b)=>(a>b?1:(a

// Define a comparator of city names
> let citiesCmp=(a,b)=>cmp(a.get('city'), b.get('city'));

// Create a SortedSet with custom comparator
> const map2=SortedMap(citiesSeq, citiesCmp);
SortedMap {
Map { "state": "MA", "city": "Boston" }: List [ "42°21′N", "71°04′W" ],
Map { "city": "Miami", "state": "FL" }: List [ "25°47′N", "80°13′W" ],
Map { "city": "Phoenix", "state": "AZ" }: List [ "33°27′N", "112°04′W" ],
Map { "city": "Seattle", "state": "WA" }: List [ "47°37′N", "122°20′W" ] }
`

The custom comparator that we have created seems to work as expected. Now let's add into the collection another city of Phoenix, this time from state Illinois.

`js
> const map3=map2.set(fromJS({city: 'Phoenix', state: 'IL'}), fromJS(['41°36′N','87°37′W']));
SortedMap {
Map { "state": "MA", "city": "Boston" }: List [ "42°21′N", "71°04′W" ],
Map { "city": "Miami", "state": "FL" }: List [ "25°47′N", "80°13′W" ],
Map { "city": "Phoenix", "state": "IL" }: List [ "41°36′N", "87°37′W" ],
Map { "city": "Seattle", "state": "WA" }: List [ "47°37′N", "122°20′W" ] }
`

The Phoenix, AZ had been replaced with Phoenix, IL. This is because of the way the custom comparator is defined. It determines equality by comparing city names only, therefore Phoenix, AZ and Phoenix, IL are equal according to this comparator. Let's try to extend the comparator to compare the city name first and if they match then determine the result by comparing the state.

`js
// Define more complex custom comparator
> citiesCmp=(a,b)=>cmp(a.get('city'), b.get('city'))||cmp(a.get('state'), b.get('state'));

// Create a new SortedMap with new custom comparator
> const map4=SortedMap(map2, citiesCmp);
SortedMap {
Map { "state": "MA", "city": "Boston" }: List [ "42°21′N", "71°04′W" ],
Map { "city": "Miami", "state": "FL" }: List [ "25°47′N", "80°13′W" ],
Map { "city": "Phoenix", "state": "AZ" }: List [ "33°27′N", "112°04′W" ],
Map { "city": "Seattle", "state": "WA" }: List [ "47°37′N", "122°20′W" ] }

// map4 looks the same as map2, now let's add the conflicting Phoenix, IL to map4
> const map5=map4.set(fromJS({city: 'Phoenix', state: 'IL'}), fromJS(['41°36′N','87°37′W']));
SortedMap {
Map { "state": "MA", "city": "Boston" }: List [ "42°21′N", "71°04′W" ],
Map { "city": "Miami", "state": "FL" }: List [ "25°47′N", "80°13′W" ],
Map { "city": "Phoenix", "state": "AZ" }: List [ "33°27′N", "112°04′W" ],
Map { "city": "Phoenix", "state": "IL" }: List [ "41°36′N", "87°37′W" ],
Map { "city": "Seattle", "state": "WA" }: List [ "47°37′N", "122°20′W" ] }
`

The custom comparator behaves as expected. Now let's swap the order of commands in the comparator and sort by state first and by city name second.

`js
> const stateCitiesCmp=(a,b)=>cmp(a.get('state'), b.get('state'))||cmp(a.get('city'), b.get('city'));

> const map6=SortedMap(map5, stateCitiesCmp);
SortedMap {
Map { "city": "Phoenix", "state": "AZ" }: List [ "33°27′N", "112°04′W" ],
Map { "city": "Miami", "state": "FL" }: List [ "25°47′N", "80°13′W" ],
Map { "city": "Phoenix", "state": "IL" }: List [ "41°36′N", "87°37′W" ],
Map { "state": "MA", "city": "Boston" }: List [ "42°21′N", "71°04′W" ],
Map { "city": "Seattle", "state": "WA" }: List [ "47°37′N", "122°20′W" ] }
`

Partial sort

Any collection (including sequences) provides partialSort() and partialSortBy()
functions for efficiently finding and sorting the n smallest elements in a collection using
Floyd-Rivest select algorithm.

Example:

`js
> const { Seq } = require('immutable-sorted');

> const seq1=Seq(['orange', 'apple', 'banana']);
> seq1.partialSort(2)
Seq [ "apple", "banana" ]
`

Incremental sort

Any collection (including sequences) also provides incSort() and incSortBy()
functions optimized to provide first entries of the result set faster than regular sort().
This function is expected to be used with iterators or sequence operations
retrieving limited number of result entries.

Example:

`js
> const { Seq } = require('immutable-sorted');

> const seq1=Seq(['orange', 'apple', 'banana']);
> seq1.incSort().take(2)
Seq [ "apple", "banana" ]
`

Comparison of filter(), groupBy(), and partition()

The filter(), groupBy(), and partition() methods are similar in that they
all divide a collection into parts based on applying a function to each element.
All three call the predicate or grouping function once for each item in the
input collection. All three return zero or more collections of the same type as
their input. The returned collections are always distinct from the input
(according to ===), even if the contents are identical.

Of these methods, filter() is the only one that is lazy and the only one which
discards items from the input collection. It is the simplest to use, and the
fact that it returns exactly one collection makes it easy to combine with other
methods to form a pipeline of operations.

The partition() method is similar to an eager version of filter(), but it
returns two collections; the first contains the items that would have been
discarded by filter(), and the second contains the items that would have been
kept. It always returns an array of exactly two collections, which can make it
easier to use than groupBy(). Compared to making two separate calls to
filter(), partition() makes half as many calls it the predicate passed to
it.

The groupBy() method is a more generalized version of partition() that can
group by an arbitrary function rather than just a predicate. It returns a map
with zero or more entries, where the keys are the values returned by the
grouping function, and the values are nonempty collections of the corresponding
arguments. Although groupBy() is more powerful than partition(), it can be
harder to use because it is not always possible predict in advance how many
entries the returned map will have and what their keys will be.

| Summary | filter | partition | groupBy` |
| :---------------------------- | :------- | :---------- | :------------- |
| ease of use | easiest | moderate | hardest |
| generality | least | moderate | most |
| laziness | lazy | eager | eager |
| # of returned sub-collections | 1 | 2 | 0 or more |
| sub-collections may be empty | yes | yes | no |
| can discard items | yes | no | no |
| wrapping container | none | array | Map/OrderedMap |

Additional Tools and Resources

- Atom-store

- A Clojure-inspired atom implementation in Javascript with configurability
for external persistance.

- Chai Immutable

- If you are using the Chai Assertion Library, this
provides a set of assertions to use against Immutable.js collections.

- Fantasy-land

- Specification for interoperability of common algebraic structures in JavaScript.

- Immutagen

- A library for simulating immutable generators in JavaScript.

- Immutable-cursor

- Immutable cursors incorporating the Immutable.js interface over
Clojure-inspired atom.

- Immutable-ext

- Fantasyland extensions for immutablejs

- Immutable-js-tools

- Util tools for immutable.js

- Immutable-Redux

- redux-immutable is used to create an equivalent function of Redux
combineReducers that works with Immutable.js state.

- Immutable-Treeutils

- Functional tree traversal helpers for ImmutableJS data structures.

- Irecord

- An immutable store that exposes an RxJS observable. Great for React.

- Mudash

- Lodash wrapper providing Immutable.JS support.

- React-Immutable-PropTypes

- PropType validators that work with Immutable.js.

- Redux-Immutablejs

- Redux Immutable facilities.

- Rxstate

- Simple opinionated state management library based on RxJS and Immutable.js.

- Transit-Immutable-js
- Transit serialisation for Immutable.js.
- See also: Transit-js

Have an additional tool designed to work with Immutable.js?
Submit a PR to add it to this list in alphabetical order.

Contributing

Use Github issues for requests.

We actively welcome pull requests, learn how to contribute.

Immutable.js is maintained within the Contributor Covenant's Code of Conduct.

$3

Changes are tracked as Github releases.

$3

Immutable.js is MIT-licensed.

$3

Phil Bagwell, for his inspiration
and research in persistent data structures.

Hugh Jackson, for providing the npm package
name. If you're looking for his unsupported package, see this repository.