如何在没有突变的情况下使用 javascript 地图
How to work with javascript Map without mutations
我在我的 JS 项目中以函数式方式工作。
这也意味着我不会变异 object 或 array 实体。相反，我总是创建一个新实例并替换旧实例。
例如
let obj = {a: 'aa', b: 'bb'}
obj = {...obj, b: 'some_new_value'}
问题是：
如何使用 javascript 地图以功能性（不可变）方式工作？
我想我可以使用下面的代码来添加值：
let map = new Map()
...
map = new Map(map).set(something)
但是删除项目呢？
我不能做 new Map(map).delete(something)，因为 .delete 的结果是布尔值。
P.S. 我知道 ImmutableJS 的存在，但我不想使用它，因为你永远无法 100% 确定你是否在工作现在使用普通 JS 对象，或使用 immutablejs 的对象（尤其是嵌套结构）。而且由于对 TypeScript 的支持不佳，顺便说一句。
I cannot do new Map(map).delete(something);, because the result of .delete is a boolean.
您可以使用间隙变量。如果你愿意，你可以将它分配给一个函数：
function map_delete(old_map, key_to_delete) {
const new_map = new Map(old_map);
new_map.delete(key_to_delete);
return new_map;
}
或者您可以创建获取映射中的条目，过滤它们并根据结果创建一个新条目：
const new_map = new Map( Array.from(old_map.entries).filter( ([key, value]) => key !== something ) );
如果您不想使用持久性地图数据结构，那么您将无法绕过突变或不得不进行极其低效的浅拷贝。请注意，突变本身并无害处，但仅与共享底层可变值有关。
如果我们能够限制访问可变值的方式，我们就能获得安全的可变数据类型。不过，它们是有代价的。你不能像往常一样使用它们。事实上，使用它们需要一些时间来熟悉。这是一个权衡。
这里是原生的例子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)}
如果您仔细查看 Mutable，您会发现它也创建了一个浅表副本，但最初只创建了一次。然后，您可以根据需要进行尽可能多的突变，直到您第一次检查可变值。
您可以在我的 scriptum library. Here is a post 中找到包含多个实例的实现，以及有关该概念的更多背景信息。
我从 Rust 那里借用了这个概念，它被称为 ownership。类型理论背景是仿射类型，属于线性类型，如果你感兴趣的话。
功能模块
这是我对持久性 map 模块的小实现 -
// 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)
展开下面的代码片段以在您自己的浏览器中验证结果 -
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}
面向对象的接口
如果你想以面向对象的方式使用它，你可以在我们的普通函数周围添加一个 class 包装器。这里我们称它为 Mapping 因为我们不想破坏原生的 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)
即使我们通过 OOP 接口调用，我们的数据结构仍然表现稳定。没有使用可变状态 -
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} }
滚动你自己的数据结构
另一种选择是编写您自己的 map 模块，该模块 不 依赖于 JavaScript 的原生 Map。这完全将我们从其可变行为中解放出来，并防止每次我们希望 set、update 或 del 时都进行完整复制。该解决方案让您可以完全控制并有效地演示如何实现您想象中的任何数据结构 -
// 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))
我们希望得到预期的输出 -
- 地图
m，fromEntries(a) 的结果
- 映射
m 的派生键 "b" 已删除
- 映射
m 的导数，密钥 "c" 已更新为 "#"
- map
m，未修改上述操作
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)
是时候实现我们的愿望并实施我们的 map 模块了。我们将从定义 empty 映射 -
的含义开始
// map.js
const empty =
Symbol("map.empty")
const isEmpty = t =>
t === empty
接下来我们需要一种方法将条目插入 map。这调用存在，fromEntries、set、update 和 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 })
接下来我们将定义一种方法来 get 来自地图的值 -
// 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
现在我们将定义一种方法来 del 从我们的地图中创建一个条目，它也调用存在 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
最后，我们提供了一种使用 toString 可视化地图的方法，它调用存在 inorder。作为奖励，我们将投入 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))
导出模块的功能-
// map.js (continued)
export { empty, isEmpty, fromEntries, get, set, update, del, append, inorder, toArray, toString }
唾手可得的果实
您的地图模块已完成，但我们可以轻松添加一些有价值的功能。下面我们实现 preorder 和 postorder 地图遍历。此外，我们向 toString 和 toArray 添加了第二个参数，允许您选择要使用的遍历。默认使用inorder-
// 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 }
而且我们可以扩展 fromEntries 以接受任何可迭代对象，而不仅仅是数组。这与 Object.fromEntries 和 Array.from -
的功能相匹配
// map.js (continued)
function fromEntries(it)
{ let r = empty
for (const [k, v] of it)
r = set(r, k, v)
return r
}
就像我们上面所做的那样，我们可以添加第二个参数，它允许我们指定如何将条目添加到地图中。现在它就像 Array.from 一样工作。为什么 Object.fromEntries 没有这种行为让我感到困惑。 Array.from 很聪明。像 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)
演示
展开下面的代码片段以在您自己的浏览器中验证我们的地图模块的结果 -
// 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"))
我在我的 JS 项目中以函数式方式工作。
这也意味着我不会变异 object 或 array 实体。相反，我总是创建一个新实例并替换旧实例。
例如
let obj = {a: 'aa', b: 'bb'}
obj = {...obj, b: 'some_new_value'}
问题是：
如何使用 javascript 地图以功能性（不可变）方式工作？
我想我可以使用下面的代码来添加值：
let map = new Map()
...
map = new Map(map).set(something)
但是删除项目呢？
我不能做 new Map(map).delete(something)，因为 .delete 的结果是布尔值。
P.S. 我知道 ImmutableJS 的存在，但我不想使用它，因为你永远无法 100% 确定你是否在工作现在使用普通 JS 对象，或使用 immutablejs 的对象（尤其是嵌套结构）。而且由于对 TypeScript 的支持不佳，顺便说一句。
I cannot do new Map(map).delete(something);, because the result of .delete is a boolean.
您可以使用间隙变量。如果你愿意，你可以将它分配给一个函数：
function map_delete(old_map, key_to_delete) {
const new_map = new Map(old_map);
new_map.delete(key_to_delete);
return new_map;
}
或者您可以创建获取映射中的条目，过滤它们并根据结果创建一个新条目：
const new_map = new Map( Array.from(old_map.entries).filter( ([key, value]) => key !== something ) );
如果您不想使用持久性地图数据结构，那么您将无法绕过突变或不得不进行极其低效的浅拷贝。请注意，突变本身并无害处，但仅与共享底层可变值有关。
如果我们能够限制访问可变值的方式，我们就能获得安全的可变数据类型。不过，它们是有代价的。你不能像往常一样使用它们。事实上，使用它们需要一些时间来熟悉。这是一个权衡。
这里是原生的例子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)}
如果您仔细查看 Mutable，您会发现它也创建了一个浅表副本，但最初只创建了一次。然后，您可以根据需要进行尽可能多的突变，直到您第一次检查可变值。
您可以在我的 scriptum library. Here is a post 中找到包含多个实例的实现，以及有关该概念的更多背景信息。
我从 Rust 那里借用了这个概念，它被称为 ownership。类型理论背景是仿射类型，属于线性类型，如果你感兴趣的话。
功能模块
这是我对持久性 map 模块的小实现 -
// 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)
展开下面的代码片段以在您自己的浏览器中验证结果 -
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}
面向对象的接口
如果你想以面向对象的方式使用它，你可以在我们的普通函数周围添加一个 class 包装器。这里我们称它为 Mapping 因为我们不想破坏原生的 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)
即使我们通过 OOP 接口调用，我们的数据结构仍然表现稳定。没有使用可变状态 -
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} }
滚动你自己的数据结构
另一种选择是编写您自己的 map 模块，该模块 不 依赖于 JavaScript 的原生 Map。这完全将我们从其可变行为中解放出来，并防止每次我们希望 set、update 或 del 时都进行完整复制。该解决方案让您可以完全控制并有效地演示如何实现您想象中的任何数据结构 -
// 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))
我们希望得到预期的输出 -
- 地图
m，fromEntries(a)的结果
- 映射
m的派生键"b"已删除 - 映射
m的导数，密钥"c"已更新为"#" - map
m，未修改上述操作
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)
是时候实现我们的愿望并实施我们的 map 模块了。我们将从定义 empty 映射 -
// map.js
const empty =
Symbol("map.empty")
const isEmpty = t =>
t === empty
接下来我们需要一种方法将条目插入 map。这调用存在，fromEntries、set、update 和 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 })
接下来我们将定义一种方法来 get 来自地图的值 -
// 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
现在我们将定义一种方法来 del 从我们的地图中创建一个条目，它也调用存在 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
最后，我们提供了一种使用 toString 可视化地图的方法，它调用存在 inorder。作为奖励，我们将投入 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))
导出模块的功能-
// map.js (continued)
export { empty, isEmpty, fromEntries, get, set, update, del, append, inorder, toArray, toString }
唾手可得的果实
您的地图模块已完成，但我们可以轻松添加一些有价值的功能。下面我们实现 preorder 和 postorder 地图遍历。此外，我们向 toString 和 toArray 添加了第二个参数，允许您选择要使用的遍历。默认使用inorder-
// 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 }
而且我们可以扩展 fromEntries 以接受任何可迭代对象，而不仅仅是数组。这与 Object.fromEntries 和 Array.from -
// map.js (continued)
function fromEntries(it)
{ let r = empty
for (const [k, v] of it)
r = set(r, k, v)
return r
}
就像我们上面所做的那样，我们可以添加第二个参数，它允许我们指定如何将条目添加到地图中。现在它就像 Array.from 一样工作。为什么 Object.fromEntries 没有这种行为让我感到困惑。 Array.from 很聪明。像 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)
演示
展开下面的代码片段以在您自己的浏览器中验证我们的地图模块的结果 -
// 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"))