Efficient means of building a tree from node records pulled from DB

building-trees-from-pg-rows.md

Sample tree:

a
|
+- b
|  |
|  +- d
|  |
|  `- e
|
`- c

Can store in database as one row per node, where we store each node's path in the tree:

* a
* a.b
* a.c
* a.b.d
* a.b.e

When we retrieve from the database, we can also pull back "level" info:

* a, 1
* a.b, 2
* a.c, 2
* a.b.d, 3
* a.b.e, 3

If we sort by each node's path, it gives us a performant means of building the tree from the Haskell side:

* a, 1
* a.b, 2
* a.b.d, 3
* a.b.e, 3
* a.c, 2

So we can use the root node as our starting point and then walk the remaining records in sequence, recursively building up each child subtree of the root by checking for increasing level info on each subsequent record.

go
  :: Int           -- current level
  -> [a]           -- not-yet-added nodes
  -> Tree a        -- root for this level
  -> ([a], Tree a) -- state of the remaining nodes + the tree at this step
go curLevel rows root =
  case rows of
    [] -> ([], root)
    label : rest ->
      if nlevel label <= curLevel then
        (rows, root)
      else
        uncurry (go curLevel)
          $ fmap (addChildTree root)
          $ go (nlevel label) rest
          $ pure
          $ f label

Tree comes from the containers package:

data Tree a = Node
  { rootLabel :: a         -- ^ label value
  , subForest :: [Tree a]  -- ^ zero or more child trees
  }