javascript - Ramda 基于键匹配的递归合并

Question

我有两个节点列表，其形状如下:

interface TreeNode {
    data: {
        name: string,
        sharedProp: boolean,
        oldProp: boolean
    },
    children: TreeNode[],
    parents: TreeNode[],
    thereAreSomeShallowProps: any,
}

完整的数据集将是一个TreeNode数组

我想要的是有一个可以遍历这棵树的函数，将 changes 树中的更改合并到基础树中。它需要的一些功能:

• 匹配指定键的值(本例支持多级键)，并合并匹配项
  • 可能与展平和groupBy
• 当对象的值为数组时，递归
• 抵抗循环引用
• 能够处理非常大的对象(至少超过 100k 个节点)

我看过的一些函数(但不确定如何组合在一起来构建我想要的函数):

• applySpec
• groupBy
• mergeWithKey
• mergeDeepWithKey

Here is a sandbox检查一下，一些测试应该可以更好地解释我想要实现的目标

Answer 1

虽然这可能不是最好的方法，但我们可以使用家里现有的工具轻松构建它。 (就我而言，我在 another StackOverflow answer 中编写了这些函数。)我在这里自由地使用了 Ramda 函数，因为问题被标记为 Ramda (免责声明:我是 Ramda 作者)，但下面我展示了构建所需的替代版本从头开始实用功能。

这假设您的更改对象将是和/或将包含稀疏数组。如果没有，您打算如何匹配？

这是我的方法:

// Helper or utility functions
function * getPaths(o, p = []) {
  if (Object(o) !== o || Object .keys (o) .length == 0) yield p 
  if (Object(o) === o)
    for (let k of Object .keys (o))
      yield * getPaths (o[k], [... p, Number.isInteger (Number (k)) ? Number (k) : k])
}

const allPaths = (o) => [... getPaths(o)]

// Main function
const applyChanges = (obj, changes) =>
  reduce ((o, p) => assocPath (p, path (p, changes), o), obj, allPaths (changes))

// Sample data
const base = [
  {a: 1, b: {c: 11, d: [{e: 100}, {e: 111}]}},
  {a: 2, b: {c: 22, d: [{e: 200}, {e: 222}]}},
  {a: 3, b: {c: 33, d: [{e: 300}, {e: 333}]}},
]

const deltas = [
  {a: 8, b: {       d: [        , {e: 888}]}},
  ,
  {      b: {c: 99, d: [{e: 999},         ]}},
]

// Demonstration
console .log (
  applyChanges (base, deltas)
)

<script src="//cdnjs.cloudflare.com/ajax/libs/ramda/0.27.0/ramda.js"></script>
<script> const {reduce, assocPath, path} = R                 </script>

allPaths 查找对象中所有叶节点的路径，其中数组索引显示为数字，其他键显示为字符串。例如，

const foo = {a: 42, b: {c: 12, d: [{e: 10}, {e: 20}]}}
allPaths (foo) //=> [["a"], ["b", "c"], ["b", "d", 0, "e"], ["b", "d", 1, "e"]]

这只是生成器函数 getPaths 的一个薄包装，它为此执行实际的递归繁重工作。我们可以编写一个简单的递归版本，但生成器通常会使编写此类遍历变得更简单。

通过更改对象中的路径列表，我们可以应用这些值来制作主对象的新副本。这是在我们的主函数 applyChanges 中完成的。它找到 changes 对象中的路径，然后使用 Ramda 的 assocPath 和 reduce 将它们折叠到我们的主对象中。

由于两个原因，我们可能会在速度和内存方面出现一些低效率。为了提高速度，当我们调用 path(p,changes) 时，我们会追踪每个路径的值，但我们已经在 getPath 中完成了适当的遍历。使用 getPath 中的 path 和 value 报告不同的结构，然后在 applyChaages< 中使用它们，可能会节省一些费用。/。这不会影响算法的复杂性，只会影响系数，而且我不会担心它，除非它被证明存在可测量的问题。至于内存，这种使用 assocPath 的 reduce 风格涉及在每次迭代时创建新对象。鉴于存在重要的结构共享，这可能不是什么大问题，但对于大型更改对象，这可能是一个问题。 (这些对我来说不是主要的担忧，但我把这类事情放在脑后。)

没有 Ramda

因为我倾向于用 Ramda 来思考，所以我使用 Ramda 工具编写了上面的内容。但只涉及到几个功能。在这种情况下，R.reduce 可以简单地替换为 Array.prototype.reduce，并且我们可以编写自己的 R.assocPath 版本并R.path 相当容易。这是另一个不使用库的版本:

// Utility functions

const isInt = Number.isInteger

const path = (ps = [], obj = {}) =>
  ps .reduce ((o, p) => (o || {}) [p], obj)

const assoc = (prop, val, obj) => 
  isInt (prop) && Array .isArray (obj)
    ? [... obj .slice (0, prop), val, ...obj .slice (prop + 1)]
    : {...obj, [prop]: val}

const assocPath = ([p = undefined, ...ps], val, obj) => 
  p == undefined
    ? obj
    : ps.length == 0
      ? assoc(p, val, obj)
      : assoc(p, assocPath(ps, val, obj[p] || (obj[p] = isInt(ps[0]) ? [] : {})), obj)


// Helper functions

function * getPaths(o, p = []) {
  if (Object(o) !== o || Object .keys (o) .length == 0) yield p 
  if (Object(o) === o)
    for (let k of Object .keys (o))
      yield * getPaths (o[k], [...p, isInt (Number (k)) ? Number (k) : k])
}

const allPaths = (o) => [... getPaths(o)]

// Main function
const applyChanges = (obj, changes) =>
  allPaths(changes).reduce((o, p) => assocPath(p, path(p, changes), o), obj)

// Sample data
const base = [
  {a: 1, b: {c: 11, d: [{e: 100}, {e: 111}]}},
  {a: 2, b: {c: 22, d: [{e: 200}, {e: 222}]}},
  {a: 3, b: {c: 33, d: [{e: 300}, {e: 333}]}},
]

const deltas = [
  {a: 8, b: {       d: [        , {e: 888}]}},
  ,
  {      b: {c: 99, d: [{e: 999},         ]}},
]

// Demonstration
console .log (
  applyChanges (base, deltas)
)

直接方法

这两个版本都使用相当间接的方法来解决问题。我碰巧有这些方便的工具，可以让我快速构建主要功能。但我确信有一种更直接的递归方法。如果我有时间，我会尝试创建一个。