我试图理解如何在 JS 中实现不可变数据结构,例如使用 trie 等。我了解到,这里应该存在重要的结构共享。
我的问题是,假设你有一个类似于下面的图结构:
a -- b
|
c
|
d -- h
|
e -- i -- l
|
f -- j -- m
|
g -- k -- n
那么你需要在系统中添加一个 x
。我会尝试两种不同的方法:
a -- b
|
c
|
d -- h -- x
|
e -- i -- l
|
f -- j -- m
|
g -- k -- n
那一个只是作为叶节点添加的。
a -- b
|
c
|
d -- h
|
x
|
e -- i -- l
|
f -- j -- m
|
g -- k -- n
那个东西被添加在路径中间。
我想知道如何使用不可变数据结构来处理这两种情况。我们有一个函数 f : graph -> graph'
,它将图形更改为“新图形”,但在底层它只应该对数据结构进行小的调整。不确定它会是什么样子或者怎么工作。我的第一个尝试是这样的解释...
它始于一个包装对象,就像 ImmutableJS 在 JS 对象之上的 API 层。
--------------------------
| |
| a -- b |
| | |
| c |
| | |
| d -- h |
| | |
| e -- i -- l |
| | |
| f -- j -- m |
| | |
| g -- k -- n |
| |
--------------------------
然后你进行更改,它会创建一个新的包装对象。
-------------------------- --------------------------
| | | |
| a -- b | | |
| | | | |
| c | | |
| | | | |
| d -- h --------------------------------- x |
| | | | |
| e -- i -- l | | |
| | | | |
| f -- j -- m | | |
| | | | |
| g -- k -- n | | |
| | | |
-------------------------- --------------------------
同样地,针对第二个例子进行操作: -------------------------- --------------------------
| | | |
| a -- b | | |
| | | | |
| c | | |
| | | | |
| d -- h | | |
| | | | |
| o --------------------------------- x |
| | | | |
| e -- i -- l | | |
| | | | |
| f -- j -- m | | |
| | | | |
| g -- k -- n | | |
| | | |
-------------------------- --------------------------
盒子是您使用的API对象,内部的图形是纯JS数据对象。
但在这些示例中,原始图形结构被修改(在第一个示例中放置到h
的链接,在第二个示例中放置一个o
占位符)。所以我想知道具体如何使这些东西不可变。我对图形进行的每个更改都希望“返回一个新对象”,但在幕后有最佳的结构共享。
感谢您的帮助。