Making a recursive function non-mutating?

Question

I have a recursive function, that removes an item by id, also if this item is nested in a children array, it will move it up one level, it's basically a sort of menu structure. When an item get's deleted, the children don't get thrown away, but stay in the original object.

Now this takes a 'data' parameter and manipulates it, but I'm wondering if it's possible to transform this into a function that returns a brand new array, keeping the argument immutable?

This is the function

function removeId(data, id, parent = null) {
  data.forEach((o, i) => {
    if (o.id && o.id === id) {
      if (parent) {
        o.children.forEach(c => parent.children.push(c));
      }
      data.splice(i, 1);
      return true;
    } else if (o.children) {
      removeId(o.children, id, o);
    }
  });
}

This is the test data used

const data = [
  {
    id: 2,
    children: [
      {
        id: 1,
        children: []
      }
    ]
  },
  {
    id: 3,
    children: [],
  }
]

The function is called like this

data = removeId(data, itemIdToDelete)

The expected output is a new (immutable) array with the structure of the previous one, except the removed items (nested)

This is the expected output after running the method and passing the id of 2 to be deleted

const data = [
  {
    id: 1,
    children: []
  },
  {
    id: 3,
    children: [],
  }
]

I've tried

Converting the function using Array.reduce() or Array.filter() but it breaks the recursiveness and returns undefined every time.

Edit: This is not just a simple deep cloning issue, there's logic involved, for example checking if a parent has children.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/slice — hindmost, Mar 26 '19 at 09:29
@Notflip bu your `removeId` method takes 3 parameters?? And what is `this.links`? — Nick Parsons, Mar 26 '19 at 09:36
@hindmost slice only returns a shallow copy, so that will never work with the nesting provided. — Miguel Stevens, Mar 26 '19 at 09:36
@Notflip Sure, `slice` is not _**ready-to-use**_ solution. But it might be useful for your function, instead of `splice`. — hindmost, Mar 26 '19 at 09:39
@NickParsons Fixed it, this.links was supposed to be data, parent is nullable, it's only used in recursion, thanks! — Miguel Stevens, Mar 26 '19 at 09:39
Possible duplicate of [What is the most efficient way to deep clone an object in JavaScript?](https://stackoverflow.com/questions/122102/what-is-the-most-efficient-way-to-deep-clone-an-object-in-javascript) — VLAZ, Mar 26 '19 at 09:44
@Bergi clone the entire input at the start of the function, then use that instead of the parameter. Wouldn't that work? — VLAZ, Mar 26 '19 at 09:59
@VLAZ Yeah that might work, but is ugly and inefficient. Also it's not a duplicate - but you can post an answer that suggests `function nonMutatingRemoveId(data, id) { return mutatingRemoveId(clone(data), id); }` — Bergi, Mar 26 '19 at 10:02
@Notflip Can you show us how you tried to use `reduce` and `filter`? If you were getting `undefined`, it sounds like you just forgot a `return` somewhere. — Bergi, Mar 26 '19 at 10:05
I don't understand why you are not deep-cloning first your array and then filter it. [It much faster](https://stackoverflow.com/a/5344074/2389232). Else you should add logic in each level of recursion to create the new array (it is the same as deep-clone...) — SnakeDrak, Mar 26 '19 at 10:20

Nenad Vracar · Accepted Answer · 2019-03-26T12:47:58.293

6

You could do this using reduce method and create new array on each level of recursion.

const data = [{"id":2,"children":[{"id":1,"children":[]}]},{"id":3,"children":[]}]

function removeId(data, id) {
  return data.reduce((r, e) => {
    // create shallow copy of the current object
    const o = Object.assign({}, e);
    
    // if object has children property
    // create nested copy of children with recursive call
    // where data param will now be children of the current element
    if(e.children) {
      o.children = removeId(e.children, id);
    }
    
    // if id of the current element is equal to target id
    // push(spread) its children to current accumulator - r
    // that will depend of the current recursion level
    // else just push current object shallow copy - o
    if (id == e.id) {
      r.push(...o.children)
    } else {
      r.push(o)
    }
    
    // return accumulator
    return r;
  }, [])
}

console.log(removeId(data, 1))
console.log(removeId(data, 3))
console.log(removeId(data, 2))

edited Mar 26 '19 at 12:47

answered Mar 26 '19 at 09:43

Nenad Vracar

118,580
15
151
176

The object with id: 1 is still included in the first console.log() I see? What needs to happen is the object with the passed id, has to be removed from the array or the children inside the array. And then the children have to move up, it's basically a menu structure – Miguel Stevens Mar 26 '19 at 09:53
Ok but that is not what you have said `also if this item is nested in a children array, it will move it up.` – Nenad Vracar Mar 26 '19 at 09:56
I meant move it up one level, sorry if it's not clear, I'll edit the question. – Miguel Stevens Mar 26 '19 at 09:56
@Notflip I am still not sure what is the result you are looking for could you provide an examples – Nenad Vracar Mar 26 '19 at 09:58
Sure let me update the question with the desired result. – Miguel Stevens Mar 26 '19 at 10:00
I updated the question, as you can see when an object (2 in our case) is deleted, it's children are pushed up one level, and are not deleted with the item we delete. – Miguel Stevens Mar 26 '19 at 10:02
It is the same as deep-clone and then to filter it. You are cloning each array in each level of recursion. – SnakeDrak Mar 26 '19 at 10:25
1

@NenadVracar - You don't need `parent` in the function declaration as you are not using it. – Euan Smith Mar 26 '19 at 10:33
Would you care explaining the steps? Recursion combined with Array Reduce is incredibly hard to grasp. – Miguel Stevens Mar 26 '19 at 12:37
@Notflip Hope that helps. – Nenad Vracar Mar 26 '19 at 12:48
Thanks for that! I'm banging my head against the wall for not being able to just read recursive functions, I guess it's something that's going to take a while. – Miguel Stevens Mar 26 '19 at 13:01

Euan Smith · Answer 2 · 2019-03-26T10:31:42.413

Instead you can do it with generators, and thus avoid all of that pushing. yield* can then be used to pull child data up a level.

const data = [{"id":2,"children":[{"id":1,"children":[]}]},{"id":3,"children":[]}]

function * _removeId(data, id){
  for(o of data){
    if(o.id===id) yield* o.children;
    else yield Object.assign({},o,{children: removeId(o.children, id)});
  }
}

function removeId(data, id){
  return Array.from(_removeId(data, id));
}

console.log(removeId(data,1));
console.log(removeId(data,2));
console.log(removeId(data,3));

Basically yield* defers array iteration to another function call, so inserts the child elements in the sequence instead of the root element if the ID matches. This also means there is no need to pass around a parent object. Object.assign deals with object cloning and Array.from ensures a new array object each time.

score 0 · Answer 3 · answered Mar 26 '19 at 11:37

You can able to do like this by creating the array recursively

const data = [
{
id: 2,
children: [
  {
    id: 1,
    children: []
  }
]
},
{
id: 3,
children: [],
}
];

function removeData(myarray, removable) {
 var branch = [];
 var datas= {};
 myarray.forEach((dat, key) => {
  if(dat.id != removable) {
     datas.id = dat.id;
     datas.children = [];
  }

 if(dat.children.length >0) {
       var children =   removeData(dat.children, removable);
       if(children && datas.id) {
            datas.children = children;
        } else {
             datas = children[0];
        } 
    }
    if(datas.children || datas.id) {
        branch.unshift(datas);
        datas ={};
    }   
 });
 return branch;
 }

 console.log(JSON.stringify(removeData(data, 2)));

http://jsfiddle.net/djky4gtq/3/

Making a recursive function non-mutating?

I've tried

3 Answers3