Recursive depth function on an array

A wonderful opportunity to learn about mutual recursion. The input can be in any order –

function makeIndex (items, indexer)
{ const append = (r, k, v) =>
    r.set(k, (r.get(k) || []).concat([ v ]))

  return items.reduce
    ( (r, i) => append(r, indexer(i), i)
    , new Map
    )
}

function makeTree (index, root = null)
{ const many = (all = []) =>
    all.map(one)

  const one = (forum = {}) =>
    ( { ...forum
      , subforums: many(index.get(forum.forumId))
      }
    )

  return many(index.get(root))
}

const input =
  [{forumId:1,parentId:null,forumName:"Main",forumDescription:"",forumLocked:false,forumDisplay:true},{forumId:2,parentId:1,forumName:"Announcements",forumDescription:"Announcements & Projects posted here",forumLocked:false,forumDisplay:true},{forumId:3,parentId:1,forumName:"General",forumDescription:"General forum, talk whatever you want here",forumLocked:false,forumDisplay:true},{forumId:4,parentId:3,forumName:"Introduction",forumDescription:"A warming introduction for newcomers here",forumLocked:false,forumDisplay:true}]

const result =
  makeTree(makeIndex(input, forum => forum.parentId))

console.log(JSON.stringify(result, null, 2))

[
  {
    "forumId": 1,
    "parentId": null,
    "forumName": "Main",
    "forumDescription": "",
    "forumLocked": false,
    "forumDisplay": true,
    "subforums": [
      {
        "forumId": 2,
        "parentId": 1,
        "forumName": "Announcements",
        "forumDescription": "Announcements & Projects posted here",
        "forumLocked": false,
        "forumDisplay": true,
        "subforums": []
      },
      {
        "forumId": 3,
        "parentId": 1,
        "forumName": "General",
        "forumDescription": "General forum, talk whatever you want here",
        "forumLocked": false,
        "forumDisplay": true,
        "subforums": [
          {
            "forumId": 4,
            "parentId": 3,
            "forumName": "Introduction",
            "forumDescription": "A warming introduction for newcomers here",
            "forumLocked": false,
            "forumDisplay": true,
            "subforums": []
          }
        ]
      }
    ]
  }
]

make it modular

Above makeIndex is written in a way that it can index any array of datum, but makeTree makes assumptions like ...forum, subforums, and forum.forumId. When we think about our code in modules, we are forced to draw lines of separation and consequently our programs become untangled.

Below, input is defined in main and so we keep all knowledge about input here –

// main.js
import { tree } from './tree'

const input =
  [{forumId:1,parentId:null,forumName:"Main",forumDescription:"",forumLocked:false,forumDisplay:true},{forumId:2,parentId:1,forumName:"Announcements",forumDescription:"Announcements & Projects posted here",forumLocked:false,forumDisplay:true},{forumId:3,parentId:1,forumName:"General",forumDescription:"General forum, talk whatever you want here",forumLocked:false,forumDisplay:true},{forumId:4,parentId:3,forumName:"Introduction",forumDescription:"A warming introduction for newcomers here",forumLocked:false,forumDisplay:true}]

const result =
  tree
    ( input                    // <- array of nodes
    , forum => forum.parentId  // <- foreign key
    , (forum, subforums) =>    // <- node reconstructor function
        ({ ...forum, subforums: subforums(forum.forumId) }) // <- primary key
    )

console.log(JSON.stringify(result, null, 2))

When I make a tree, I don’t want to have to think about making an index first. In our original program, how was I supposed to know a tree needed an index? Let’s let the tree module worry about that –

// tree.js
import { index } from './index'

const empty =
  {}

function tree (all, indexer, maker, root = null)
{ const cache =
    index(all, indexer)

  const many = (all = []) =>
    all.map(x => one(x))
                             // zero knowledge of forum object shape
  const one = (single) =>
    maker(single, next => many(cache.get(next)))

  return many(cache.get(root))
}

export { empty, tree } // <-- public interface

We could have written the index function directly in the tree module but the behavior we want is not specific to trees. Writing a separate index module makes more sense –

// index.js
const empty = _ =>
  new Map

const update = (r, k, t) =>
  r.set(k, t(r.get(k)))

const append = (r, k, v) =>
  update(r, k, (all = []) => [...all, v])

const index = (all = [], indexer) =>
  all.reduce
      ( (r, v) => append(r, indexer(v), v) // zero knowledge of v shape
      , empty()
      )

export { empty, index, append } // <-- public interface

Writing modules helps you think about your code in meaningful parts and promotes a high degree of code reusability.