CODEWITHSUNDEEP
javascriptfunctional-programmingramda.js
merajsahebdar
merajsahebdar

Reputation: 58

Deep Find, Remove, Update in a hierarchical array

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.

Upvotes: 1

Views: 256

Answers (1)

Mulan
Mulan

Reputation: 135237

delete a node and its descendants

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

  1. del accepts an array of nodes, t, a query, q, and calls del1 on each node with the query
  2. 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 -

  1. filter is a specialised form of flatmap
  2. 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" ]

Upvotes: 1

Related Questions