Recursive function to add object into deeply nested array of objects adding into wrong object

Solution 1:

Given immutable helper splice(a, k, trans) where -

• a is the input array
• k is the key (index) to update
• trans is a function that receives the element at k and returns a replacement value
• returns a new array with trans(a[k]) inserted at position k. Input a is not modified.

// splice :: ('a array, int, 'a -> 'a) -> 'a array
function splice(a, k, trans) {
  return a.slice(0, k).concat(trans(a[k])).concat(a.slice(k + 1))
}

And immutable helper extract(t, path) where -

• t is a node from your tree in the shape of { id, type, children? }
• path is an array of indexes
• returns [selected, tprime] where selected is the node at the end of path and tprime is a new tree with selected removed from it. The input tree t is not mutated.

This implementation takes special care to follow only a valid path of indexes. extract will throw an error when trying to get the descendant of a FILE or when node.type is neither FOLDER nor FILE -

// extract :: ('a tree, int array) -> ('a, 'a tree)
function extract(t, path) {
  function loop(t, [i, ...path], cont) {
    if (i == null)
      return cont(t, _ => [])
    else switch (t?.type) {
      case "FOLDER":
        return loop(t.children[i], path, (selected, trans) =>
          cont(selected, a => ({ ...a, children: splice(a.children, i, trans) }))
        )
      case "FILE":
        throw Error(`cannot get descendant of file: ${JSON.stringify(t)}`)
      default:
        throw Error(`unsupported type: ${JSON.stringify(t)}`)
    }
  }
  return path.length == 0
    ? [undefined, t]
    : loop(t, path, (selected, trans) => [selected, trans(t)])
}

Given an input tree, mytree, note a root node was added so there is at most one root node -

const mytree = {
  id: "root",
  type: "FOLDER",
  children: [
    {
      id: "foo",
      type: "FOLDER",
      children: [
        { id: "foo1", type: "FILE" },
        { id: "foo2", type: "FILE" }
      ]
    },
    {
      id: "bar",
      type: "FOLDER",
      children: [
        { id: "bar1", type: "FILE" }
      ]
    }
  ]
}

Let's extract foo2 by following the indexes, [0,1]

const [selected, tprime] = extract(mytree, [0,1])
console.log("selected", selected)
console.log("new tree", tprime)

selected {
  id: "foo2",
  type: "FILE"
}

new tree {
  id: "root",
  type: "FOLDER",
  children: [
    {
      id: "foo",
      type: "FOLDER",
      children: [
        { id: "foo1", type: "FILE" }
      ]
    },
    {
      id: "bar",
      type: "FOLDER",
      children: [
        { id: "bar1", type: "FILE" }
      ]
    }
  ]
}

We could extract all of bar by selecting [1] -

const [selected, tprime] = extract(mytree, [1])
console.log("selected", selected)
console.log("new tree", tprime)

selected {
  id: "bar",
  type: "FOLDER",
  children: [
    { id: "bar1", type: "FILE" }
  ]
}

new tree {
  id: "root",
  type: "FOLDER",
  children: [
    {
      id: "foo",
      type: "FOLDER",
      children: [
        { id: "foo1", type: "FILE" },
        { id: "foo2", type: "FILE" }
      ]
    }
  ]
}

In just 26 lines of code, we already solved more than half of the problem. Node insertion is significantly easier and is left as an exercise for the reader -

function insert(t, path, node) {
  //...
}

function move(t, srcPath, destPath) {
  const [selectedNode, newTree] = extract(t, srcPath)
  return insert(newTree, destPath, selectedNode)
}

For a full demonstration of the code in this post, expand the snippet below and verify the result in your own browser -

function splice(a, k, trans) {
  return a.slice(0, k).concat(trans(a[k])).concat(a.slice(k + 1))
}

function extract(t, path) {
  function loop(t, [i, ...path], cont) {
    if (i == null)
      return cont(t, _ => [])
    else switch (t?.type) {
      case "FOLDER":
        return loop(t.children[i], path, (selected, trans) =>
          cont(selected, a => ({ ...a, children: splice(a.children, i, trans) }))
        )
      case "FILE":
        throw Error(`cannot get descendant of file: ${JSON.stringify(t)}`)
      default:
        throw Error(`unsupported type: ${JSON.stringify(t)}`)
    }
  }
  return path.length == 0
    ? [undefined, t]
    : loop(t, path, (selected, trans) => [selected, trans(t)])
}

const t = 
  { id: "root", type: "FOLDER", children: [
    { id: "foo", type: "FOLDER", children: [
      { id: "foo1", type: "FILE" },
      { id: "foo2", type: "FILE" }
    ]},
    { id: "bar", type: "FOLDER", children: [
      { id: "bar1", type: "FILE" }
    ]}
  ]}
  
const [selected, tprime] = extract(t, [0,0])
console.log("selected", selected)
console.log("new tree", tprime)