haskell - 从数据库行构建树

Question

我需要从数据库行构建一棵树。更具体地说，我有一个包含会计科目表的表格。

我不想递归地查询表，而是想一步加载所有表的信息、包含 ids 和 ParentId 的帐户行，然后从那里构建树。

这样做的问题之一是帐户行不按任何顺序排列，即。我可能会在遇到 parent 之前先遇到 child 。

我认为这个问题非常普遍，所以我认为甚至可能已经有一个针对它的 haskell 库。

有人可以帮忙吗？

Answer 1

正如尼基塔所说，你真正的问题是什么？

您没有提供任何数据类型、树键分类...

无论如何，这段代码可以帮助思考你的问题......

data Tree a = Node a [Tree a] deriving Show

db = [(0, 1)
     ,(1, 2)
     ,(1, 3)
     ,(2, 4)
     ,(2, 6)
     ,(3, 5)
     ]

rootTree = Node 0 []

insert parent child (Node key childs) =
  Node key $ if key == parent then Node child []:childs
                              else map (insert parent child) childs

insertFromDB rows = foldl insertRow rootTree rows
  where insertRow tree (parent, child) = insert parent child tree

如果无法获得有序数据，可以排序搜索父节点，下一个函数计算每个节点的深度(具有相同的db数据)

calculateDeepLevel db = compute 0 roots
  where roots = filter (not.flip elem snds) fsts
        fsts = nub $ map fst db
        snds = map snd db
        compute level parents = map (\n -> (n, level)) parents ++
                                concatMap (addChilds (level + 1)) parents
        addChilds level node = compute level $ map snd $ filter ((node==).fst) db

使用calculateDeepLevel，您可以从db的无序且无根(没有0节点)版本计算有序的db版本和基于0的版本>.