Deep Find, Remove, Update in a hierarchical array

Question

Let's assume we have a tree like:

const items = [
    {
        "id": 1
    },
    {
        "id": 2,
        "items": [
            {
                "id": 3
            },
            {
                "id": 4,
                "items": []
            }
        ]
    }
];

I'm looking for an efficient way to remove/update an item by its unique id; the main issue is we do not know the exact path of item, and worse: the tree may have n levels, and what we have is just an id.

The answer from @Thankyou is great. Ramda will likely not offer much help here, as Ramda is not particularly well designed to work recursively, and this is definitely a recursive problem. — Scott Sauyet, Sep 16 '20 at 03:12

Mulan · Accepted Answer · 2020-09-16T01:23:17.363

delete a node and its descendants

Here's an effective technique using flatMap and mutual recursion -

del accepts an array of nodes, t, a query, q, and calls del1 on each node with the query
del1 accepts a single node, t, a query, q, and calls del on a node's items

const del = (t = [], q = null) =>
  t.flatMap(v => del1(v, q))            // <-- 1

const del1 = (t = {}, q = null) =>
  q == t.id
    ? []
    : { ...t, items: del(t.items, q) }  // <-- 2

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

const result =
  del(data, 3)

console.log(result)

In the output, we see node.id 3 is removed -

[
  {
    "id": 1,
    "items": []
  },
  {
    "id": 2,
    "items": [
      {
        "id": 4,
        "items": []
      }
    ]
  }
]

What if we only want to delete the parent but somehow keep the parent's items in the tree? Is there a way to write it without mutual recursion? Learn more about this technique in this related Q&A.

everything is reduce

If you know filter but haven't used flatmap yet, you might be surprised to know that -

filter is a specialised form of flatmap
flatmap is a specialised form of reduce

const identity = x =>
  x

const filter = (t = [], f = identity) =>
  flatmap                                      // 1
    ( t
    , v => f(v) ? [v] : []
    )

const flatmap = (t = [], f = identity) =>
  t.reduce                                     // 2
    ( (r, v) => r.concat(f(v))
    , []
    )
    
const input =
  [ "sam", "alex", "mary", "rat", "jo", "wren" ]
  
const result =
  filter(input, name => name.length > 3)
  
console.log(result)
// [ "alex", "mary", "wren" ]

Thanks :D Amazing! I've also read your linked Q&A. But still can't figure out in case of updating one item what should we do? — merajsahebdar, Sep 16 '20 at 01:26
_"in case of updating one item"_? I don't know what you mean — Mulan, Sep 16 '20 at 02:05
I love this as always. My preference would be for an arbitrary predicate in place of your query parameter. And I think both instances of "is a specialised form of" really should be written "can be implemented using". `reduce` is so powerful that many Array methods can be written using it. But that doesn't mean, except in the narrowest technical sense, that they're specializations of it. — Scott Sauyet, Sep 16 '20 at 03:16
I mean instead of removing an item with specific id, updating it, changing other properties on that item. update `{id: 1, name: "Max"}` to `{id: 1, name: "Alex"}`. — merajsahebdar, Sep 16 '20 at 06:04

Deep Find, Remove, Update in a hierarchical array

1 Answers1