Ramda fusión recursiva basada en la coincidencia de teclas

2020-02-21 javascript recursion functional-programming ramda.js

Tengo dos listas de nodos, que tienen esta forma:

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

El conjunto de datos completo sería una matriz de TreeNode

Lo que me gustaría es tener una función que pueda recorrer este árbol, fusionando los cambios en un árbol de changes en el árbol base. Algunas de las características que necesitaría:

  • Haga coincidir los valores de una clave especificada (en este caso, admite claves de varios niveles) y combine las coincidencias
    • posiblemente con flatten y groupBy
  • Cuando los valores del objeto son matrices, recurse
  • Resistente a referencias circulares.
  • Capaz de trabajar con objetos muy grandes (más de 100k nodos, al menos)

Algunas de las funciones que he visto (pero no estoy seguro de cómo unirlas para crear la función que quiero):

  • applySpec
  • groupBy
  • mergeWithKey
  • mergeDeepWithKey

Aquí hay un sandbox para revisar, con algunas pruebas que deberían explicar mejor lo que estoy tratando de lograr

Answers

Si bien este puede no ser el mejor enfoque, es uno que podemos construir fácilmente con las herramientas que tenemos en la casa. (En mi caso, con las que escribí en otra respuesta de StackOverflow ). Utilicé libremente las funciones de Ramda aquí, ya que la pregunta estaba etiquetada como Ramda (descargo de responsabilidad: soy un autor de Ramda), pero a continuación muestro una versión alternativa que construye la requerida funciones de utilidad desde cero.

Esto supone que su objeto de cambios será y / o incluirá matrices dispersas. Si no, ¿cómo planeas unir las cosas?

Aquí está mi enfoque:

// 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 encuentra las rutas a todos los nodos de hoja en un objeto, con los índices de matriz mostrados como números y otras claves como cadenas. Por ejemplo,

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"]]

Eso es solo una envoltura delgada alrededor de la función getPaths del generador, que hace el trabajo pesado recursivo real para esto. Podríamos escribir una versión simple y recursiva de esto, pero los generadores a menudo simplifican la escritura de tales recorridos.

Con una lista de rutas en el objeto de cambios, podemos aplicar los valores para hacer una nueva copia de nuestro objeto principal. Esto se hace en applyChanges , nuestra función principal. Encuentra las rutas en el objeto de changes , y luego usa el assocPath de assocPath y reduce para doblarlas en nuestro objeto principal.

Aquí podríamos tener algunas ineficiencias en velocidad y memoria por dos razones. Para la velocidad, estamos persiguiendo el valor en cada ruta cuando llamamos a la path(p, changes) , pero ya habíamos hecho el recorrido apropiado en getPath . Probablemente habría algunos ahorros al informar una estructura diferente con path y value fuera de getPath y luego usarlos en applyChages . Esto no afecta la complejidad algorítmica, solo los coeficientes, y no me preocuparía a menos que resulte tener problemas medibles. En cuanto a la memoria, este estilo de reduce con assocPath implica la creación de nuevos objetos en cada iteración. Dado que existe un intercambio estructural importante, esto puede no ser un gran problema, pero para un objeto de grandes changes , esto podría ser un problema. (Estas no serían grandes preocupaciones para mí, pero mantengo ese tipo de cosas en mi cabeza).

Sin Ramda

Como tiendo a pensar en Ramda, escribí lo anterior usando las herramientas de Ramda. Pero solo hay unas pocas funciones involucradas. R.reduce puede ser reemplazado trivialmente en este caso por Array.prototype.reduce , y podemos escribir nuestras propias versiones de R.assocPath y R.path bastante facilidad. Aquí hay otra versión que no usa biblioteca:

// 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)
)

Acercamiento directo

Estas dos versiones utilizan un enfoque bastante indirecto del problema. Resulta que tengo a mano estas herramientas que me permiten construir la función principal rápidamente. Pero estoy seguro de que hay un enfoque recursivo más directo. Si encuentro tiempo, buscaré crear uno.

Related