从数据库行构建一棵树

Question

我需要从数据库行构建一棵树。更具体地说，我有一张桌子，里面包含了会计科目表。

而不是递归查询表我希望加载所有表的信息，在一个步骤中包含ids和parentIds帐户行，然后从那里建立树。

这样做的问题之一是帐户行不是以任何顺序，即。在遇到父母之前，我可能会遇到一个孩子。

我认为这个问题是非常通用的，所以我推测可能已经有一个haskell库了。

任何人都可以帮忙吗？

Answer 1

在StackOverflow中获得答案的质量几乎完全取决于您提供的问题的质量。如果你想得到一个包含一些代码的答案，你应该在你的问题中提供一些代码，如果你想得到关于某个特定库的答案，那么就参考它。

目前您的问题非常模糊，我可以回答的是您需要使用类似Data.Map的结构先累积中间结果，然后通过查询此中间数据​​结构重新排列它们。正如它的文档所表示的，其大部分访问函数的复杂性是O(log n)，这非常有效。

您不应该期望来自任何数据库库的那种功能，因为问题太具体。

Answer 2

正如Nikita所说，你真正的问题是什么？

你不提供任何数据类型，树键分类，...

不管怎么说，这个代码可以帮助想想你的问题......

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可以CAL从有序和无根（没有0节点）版本的db中收集有序的db版本和基于0的版本。

Answer 3

一是部分进口，

import qualified Data.Map as M 
import qualified Data.Tree as T 
import Data.List (foldl') 
import Control.Arrow ((&&&)) 
import Data.Maybe (fromMaybe) 

接下来，让我们假设我们有一个有一个ID，以及一个可选的父ID（根节点没有父）记录，并进行一定的价值：

data Rec a = Rec { recId  :: Int 
       , recParentId :: Maybe Int 
       , recValue :: a 
       } 

没有什么可以阻止多个节点拥有一个Nothing父ID，所以我们可能会找到多个树，所以我们用于将列表转换为树的功能如下所示：

toTree :: [Rec a] -> [T.Tree a] 
toTree rs = ts where 

首先，让我们来构建从可选的父ID的地图，那有父ID记录的列表：

-- gs :: M.Map (Maybe Int) [Rec a] 
    gs = foldl' f M.empty rs where 
     f m r = M.insertWith (const (r:)) (recParentId r) [r] m 

接下来，让我们展开一个树从一个虚拟的根节点开始，的孩子这将是我们感兴趣的树根注意，虚拟根节点没有价值，所以我们使用undefined：

-- t :: T.Tree a 
    t = T.unfoldTree mkNode (undefined, Nothing) 

的mkNode函数传递我们想要的节点的值和id建立。它返回值，并利用我们构建了Map较早孩子值/ ID对的列表：

-- mkNode :: (a, Maybe Int) -> (a, [(a, Maybe Int)]) 
    mkNode (a, i) = (a, map (recValue &&& Just . recId) 
          . fromMaybe [] 
          . M.lookup i $ gs) 

最后，我们可以丢弃虚拟根节点，并返回其直接孩子为树的根我们感兴趣的是：

ts = T.subForest t 

而且这是一个测试：

main = mapM_ (putStrLn . T.drawTree) 
     $ toTree [ Rec 0 Nothing "rootA" 
        , Rec 1 (Just 0) "rootA.childA" 
        , Rec 2 (Just 0) "rootA.childB" 
        , Rec 3 (Just 1) "rootA.childA.childA" 
        , Rec 4 (Just 1) "rootA.childA.childB" 
        , Rec 5 (Just 2) "rootA.childB.childA" 
        , Rec 6 (Just 2) "rootA.childB.childB" 
        , Rec 7 Nothing "rootB" 
        , Rec 8 (Just 7) "rootB.childA" 
        , Rec 9 (Just 7) "rootB.childB" 
        , Rec 10 (Just 8) "rootB.childA.childA" 
        , Rec 11 (Just 8) "rootB.childA.childB" 
        , Rec 12 (Just 9) "rootB.childB.childA" 
        , Rec 13 (Just 9) "rootB.childB.childB" 
        ] 

产生：

rootB 
| 
+- rootB.childB 
| | 
| +- rootB.childB.childB 
| | 
| `- rootB.childB.childA 
| 
`- rootB.childA 
    | 
    +- rootB.childA.childB 
    | 
    `- rootB.childA.childA 

rootA 
| 
+- rootA.childB 
| | 
| +- rootA.childB.childB 
| | 
| `- rootA.childB.childA 
| 
`- rootA.childA 
    | 
    +- rootA.childA.childB 
    | 
    `- rootA.childA.childA