How to work with javascript Map without mutations

Question

I'm working in a functional way in my JS project.

That's also means I do not mutate object or array entities. Instead I always create a new instance and replace an old one.

e.g.

let obj = {a: 'aa', b: 'bb'}
obj = {...obj, b: 'some_new_value'}

The question is:

How to work in a functional (immutable) way with javascript Maps?

I guess I can use the following code to add values:

let map = new Map()
...
map = new Map(map).set(something)

But what about delete items?

I cannot do new Map(map).delete(something), because the result of .delete is a boolean.

P.S. I'm aware of existence of ImmutableJS, but I don't want to use it due to you never 100% sure if you are working now with a plain JS object, or with immutablejs' object (especially nested structures). And because of bad support of TypeScript, btw.

Answer 1

I cannot do new Map(map).delete(something);, because the result of .delete is a boolean.

You can use an interstitial variable. You can farm it out to a function if you like:

function map_delete(old_map, key_to_delete) {
    const new_map = new Map(old_map);
    new_map.delete(key_to_delete);
    return new_map;
} 

Or you can create get the entries in the map, filter them and create a new one from the result:

const new_map = new Map( Array.from(old_map.entries).filter( ([key, value]) => key !== something ) );

Answer 2

If you don't want to use a persistent map data structure, then you cannot get around mutations or have to conduct insanely inefficient shallow copies. Please note that mutations themselves aren't harmful, but only in conjunction with sharing the underlying mutable values.

If we are able to limit the way mutable values can be accessed, we can get safe mutable data types. They come at a cost, though. You cannot just use them as usual. As a matter of fact using them takes some time to get familiar with. It's a trade-off.

Here is an example with the native Map:

// MUTABLE

const Mutable = clone => refType => // strict variant
  record(Mutable, app(([o, initialCall, refType]) => {
    o.mutable = {
      run: k => {
        o.mutable.run = _ => {
          throw new TypeError("illegal subsequent inspection");
        };

        o.mutable.set = _ => {
          throw new TypeError("illegal subsequent mutation");
        };

        return k(refType);
      },

      set: k => {
        if (initialCall) {
          initialCall = false;
          refType = clone(refType);
        }

        k(refType);
        return o;
      }
    }

    return o;
  }) ([{}, true, refType]));
  
const mutRun = k => o =>
  o.mutable.run(k);

const mutSet = k => o =>
  o.mutable.set(k);

// MAP

const mapClone = m => new Map(m);

const mapDelx = k => m => // safe-in-place-update variant
  mutSet(m_ =>
    m_.has(k)
      ? m_.delete(k)
      : m_) (m);
      
const mapGet = k => m =>
  m.get(k);

const mapSetx = k => v => // safe-in-place-update variant
  mutSet(m_ => m_.set(k, v));

const mapUpdx = k => f => // safe-in-place-update variant
  mutSet(m_ => m_.set(k, f(m_.get(k))));

const MutableMap = Mutable(mapClone);

// auxiliary functions

const record = (type, o) => (
  o[Symbol.toStringTag] = type.name || type, o);

const app = f => x => f(x);

const id = x => x;

// MAIN

const m = MutableMap(new Map([[1, "foo"], [2, "bar"], [3, "baz"]]));

mapDelx(2) (m);
mapUpdx(3) (s => s.toUpperCase()) (m);

const m_ = mutRun(Array.from) (m);
console.log(m_); // [[1, "foo"], [3, "BAZ"]]

try {mapSetx(4) ("bat") (m)} // illegal subsequent mutation
catch (e) {console.log(e.message)}

try {mutRun(mapGet(1)) (m)} // illegal subsequent inspection
catch (e) {console.log(e.message)}

If you take a closer look at Mutable you see it creates a shallow copy as well, but only once, initially. You can than conduct as many mutations as you want, until you inspect the mutable value the first time.

You can find an implementation with several instances in my scriptum library. Here is a post with some more background information on the concept.

I borrowed the concept from Rust where it is called ownership. The type theoretical background are affine types, which are subsumed under linear types, in case you are interested.

Answer 3

roll your own data structure

Another option is to write your own map module that does not depend on JavaScript's native Map. This completely frees us from its mutable behaviours and prevents making full copies each time we wish to set, update, or del. This solution gives you full control and effectively demonstrates how to implement any data structure of your imagination -

// main.js

import { fromEntries, set, del, toString } from "./map.js"

const a =
  [["d",3],["e",4],["g",6],["j",9],["b",1],["a",0],["i",8],["c",2],["h",7],["f",5]]

const m =
  fromEntries(a)

console.log(1, toString(m))
console.log(2, toString(del(m, "b")))
console.log(3, toString(set(m, "c", "#")))
console.log(4, toString(m))

We wish for the expected output -

1. map m, the result of fromEntries(a)
2. derivative of map m with key "b" deleted
3. derivative of map m with key "c" updated to "#"
4. map m, unmodified from the above operations

1 (a, 0)->(b, 1)->(c, 2)->(d, 3)->(e, 4)->(f, 5)->(g, 6)->(h, 7)->(i, 8)->(j, 9)
2 (a, 0)->(c, 2)->(d, 3)->(e, 4)->(f, 5)->(g, 6)->(h, 7)->(i, 8)->(j, 9)
3 (a, 0)->(b, 1)->(c, #)->(d, 3)->(e, 4)->(f, 5)->(g, 6)->(h, 7)->(i, 8)->(j, 9)
4 (a, 0)->(b, 1)->(c, 2)->(d, 3)->(e, 4)->(f, 5)->(g, 6)->(h, 7)->(i, 8)->(j, 9)

Time to fulfill our wishes and implement our map module. We'll start by defining what it means to be an empty map -

// map.js

const empty =
  Symbol("map.empty")

const isEmpty = t =>
  t === empty

Next we need a way to insert our entries into the map. This calls into existence, fromEntries, set, update, and node -

// map.js (continued)

const fromEntries = a =>
  a.reduce((t, [k, v]) => set(t, k, v), empty)

const set = (t, k, v) =>
  update(t, k, _ => v)

const update = (t, k, f) =>
  isEmpty(t)
    ? node(k, f())
: k < t.key
    ? node(t.key, t.value, update(t.left, k, f), t.right)
: k > t.key
    ? node(t.key, t.value, t.left, update(t.right, k, f))
: node(k, f(t.value), t.left, t.right)

const node = (key, value, left = empty, right = empty) =>
  ({ key, value, left, right })

Next we'll define a way to get a value from our map -

// main.js (continued)

const get = (t, k) =>
  isEmpty(t)
    ? undefined
: k < t.key
    ? get(t.left, k)
: k > t.key
    ? get(t.right, k)
: t.value

And now we'll define a way to delete an entry from our map, which also calls into existence concat -

// map.js (continued)

const del = (t, k) =>
  isEmpty(t)
    ? t
: k < t.key
    ? node(t.key, t.value, del(t.left, k), t.right)
: k > t.key
    ? node(t.key, t.value, t.left, del(t.right, k))
: concat(t.left, t.right)

const concat = (l, r) =>
  isEmpty(l)
    ? r
: isEmpty(r)
    ? l
: r.key < l.key
    ? node(l.key, l.value, concat(l.left, r), l.right)
: r.key > l.key
    ? node(l.key, l.value, l.left, concat(l.right, r))
: r

Finally we provide a way to visualize the map using toString, which calls into existence inorder. As a bonus, we'll throw in toArray -

const toString = (t) =>
  Array.from(inorder(t), ([ k, v ]) => `(${k}, ${v})`).join("->")

function* inorder(t)
{ if (isEmpty(t)) return
  yield* inorder(t.left)
  yield [ t.key, t.value ]
  yield* inorder(t.right)
}

const toArray = (t) =>
  Array.from(inorder(t))

Export the module's features -

// map.js (continued)

export { empty, isEmpty, fromEntries, get, set, update, del, append, inorder, toArray, toString }

---

low hanging fruit

Your Map module is finished but there are some valuable features we can add without requiring much effort. Below we implement preorder and postorder map traversals. Additionally we add a second parameter to toString and toArray that allows you to choose which traversal to use. inorder is used by default -

// map.js (continued)

function* preorder(t)
{ if (isEmpty(t)) return
  yield [ t.key, t.value ]
  yield* preorder(t.left)
  yield* preorder(t.right)
}

function* postorder(t)
{ if (isEmpty(t)) return
  yield* postorder(t.left)
  yield* postorder(t.right)
  yield [ t.key, t.value ]
}

const toArray = (t, f = inorder) =>
  Array.from(f(t))

const toString = (t, f = inorder) =>
  Array.from(f(t), ([ k, v ]) => `(${k}, ${v})`).join("->")

export { ..., preorder, postorder }

And we can extend fromEntries to accept any iterable, not just arrays. This matches the functionality of Object.fromEntries and Array.from -

// map.js (continued)

function fromEntries(it)
{ let r = empty
  for (const [k, v] of it)
    r = set(r, k, v)
  return r
}

Like we did above, we can add a second parameter which allows us to specify how the entries are added into the map. Now it works just like Array.from. Why Object.fromEntries doesn't have this behaviour is puzzling to me. Array.from is smart. Be like Array.from -

// map.js (continued)

function fromEntries(it, f = v => v)
{ let r = empty
  let k, v
  for (const e of it)
    ( [k, v] = f(e)
    , r = set(r, k, v)
    )
  return r
}

// main.js

import { fromEntries, toString } from "./map.js"

const a =
  [["d",3],["e",4],["g",6],["j",9],["b",1],["a",0],["i",8],["c",2],["h",7],["f",5]]

const z =
  fromEntries(a, ([ k, v ]) => [ k.toUpperCase(), v * v ])

console.log(toString(z))

(A, 0)->(B, 1)->(C, 4)->(D, 9)->(E, 16)->(F, 25)->(G, 36)->(H, 49)->(I, 64)->(J, 81)

---

demo

Expand the snippet below to verify the results of our Map module in your own browser -

// map.js
const empty =
  Symbol("map.empty")

const isEmpty = t =>
  t === empty

const node = (key, value, left = empty, right = empty) =>
  ({ key, value, left, right })

const fromEntries = a =>
  a.reduce((t, [k, v]) => set(t, k, v), empty)

const get = (t, k) =>
  isEmpty(t)
    ? undefined
: k < t.key
    ? get(t.left, k)
: k > t.key
    ? get(t.right, k)
: t.value

const set = (t, k, v) =>
  update(t, k, _ => v)

const update = (t, k, f) =>
  isEmpty(t)
    ? node(k, f())
: k < t.key
    ? node(t.key, t.value, update(t.left, k, f), t.right)
: k > t.key
    ? node(t.key, t.value, t.left, update(t.right, k, f))
: node(k, f(t.value), t.left, t.right)

const del = (t, k) =>
  isEmpty(t)
    ? t
: k < t.key
    ? node(t.key, t.value, del(t.left, k), t.right)
: k > t.key
    ? node(t.key, t.value, t.left, del(t.right, k))
: concat(t.left, t.right)

const concat = (l, r) =>
  isEmpty(l)
    ? r
: isEmpty(r)
    ? l
: r.key < l.key
    ? node(l.key, l.value, concat(l.left, r), l.right)
: r.key > l.key
    ? node(l.key, l.value, l.left, concat(l.right, r))
: r

function* inorder(t)
{ if (isEmpty(t)) return
  yield* inorder(t.left)
  yield [ t.key, t.value ]
  yield* inorder(t.right)
}

const toArray = (t) =>
  Array.from(inorder(t))

const toString = (t) =>
  Array.from(inorder(t), ([ k, v ]) => `(${k}, ${v})`).join("->")
  
// main.js
const a =
  [["d",3],["e",4],["g",6],["j",9],["b",1],["a",0],["i",8],["c",2],["h",7],["f",5]]

const m =
  fromEntries(a)

console.log(1, toString(m))
console.log(2, toString(del(m, "b")))
console.log(3, toString(set(m, "c", "#")))
console.log(4, toString(m))
console.log(5, get(set(m, "z", "!"), "z"))

Answer 4

functional module

Here's my little implementation of a persistent map module -

// map.js

import { effect } from "./func.js"

const empty = _ =>
  new Map

const update = (t, k, f) =>
  fromEntries(t).set(k, f(get(t, k)))

const set = (t, k, v) =>
  update(t, k, _ => v)

const get = (t, k) =>
  t.get(k)

const del = (t, k) =>
  effect(t => t.delete(k))(fromEntries(t))

const fromEntries = a =>
  new Map(a)

export { del, empty, fromEntries, get, set, update }

// func.js
const effect = f => x =>
  (f(x), x)

// ...

export { effect, ... }

// main.js
import { fromEntries, del, set } from "./map.js"

const q =
  fromEntries([["a",1], ["b",2]])

console.log(1, q)
console.log(2, del(q, "b"))
console.log(3, set(q, "c", 3))
console.log(4, q)

Expand the snippet below to verify the results in your own browser -

const effect = f => x =>
  (f(x), x)

const empty = _ =>
  new Map

const update = (t, k, f) =>
  fromEntries(t).set(k, f(get(t, k)))

const set = (t, k, v) =>
  update(t, k, _ => v)

const get = (t, k) =>
  t.get(k)

const del = (t, k) =>
  effect(t => t.delete(k))(fromEntries(t))

const fromEntries = a =>
  new Map(a)

const q =
  fromEntries([["a", 1], ["b", 2]])

console.log(1, q)
console.log(2, del(q, "b"))
console.log(3, set(q, "c", 3))
console.log(4, q)

1 Map(2) {a => 1, b => 2}
2 Map(1) {a => 1}
3 Map(3) {a => 1, b => 2, c => 3}
4 Map(2) {a => 1, b => 2}

---

object-oriented interface

If you want to use it in an object-oriented way, you can add a class wrapper around our plain functions. Here we call it Mapping because we don't want to clobber the native Map -

// map.js (continued)

class Mapping
{ constructor(t) { this.t = t }
  update(k,f) { return new Mapping(update(this.t, k, f)) }
  set(k,v) { return new Mapping(set(this.t, k, v)) }
  get(k) { return get(this.t, k) }
  del(k) { return new Mapping(del(this.t, k)) }
  static empty () { return new Mapping(empty()) }
  static fromEntries(a) { return new Mapping(fromEntries(a))
  }
}

export default Mapping

// main.js

import Mapping from "./map"

const q =
  Mapping.fromEntries([["a", 1], ["b", 2]]) // <- OOP class method

console.log(1, q)
console.log(2, q.del("b"))      // <- OOP instance method
console.log(3, q.set("c", 3))   // <- OOP instance method
console.log(4, q)

Even though we're calling through OOP interface, our data structure still behaves persistently. No mutable state is used -

1 Mapping { t: Map(2) {a => 1, b => 2} }
2 Mapping { t: Map(1) {a => 1} }
3 Mapping { t: Map(3) {a => 1, b => 2, c => 3} }
4 Mapping { t: Map(2) {a => 1, b => 2} }