データベースの行からツリーを構築する必要があります。より具体的には、勘定科目表を含むテーブルがあります。
テーブルを再帰的にクエリする代わりに、すべてのテーブルの情報、ID と parentIds を含むアカウント行を 1 つのステップでロードし、そこからツリーを構築したいと考えています。
これに関する問題の 1 つは、アカウントの行が順不同であることです。親に会う前に子供に会うことができました。
この問題は非常に一般的であると考えているため、すでに haskell ライブラリが存在する可能性があると思います。
誰でも助けることができますか？
ニキータが言ったように、あなたの本当の問題は何ですか?
データ型、ツリーキーの分類などを提供しません...
とにかく、このコードはあなたの問題について考えるのに役立ちます...
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
を使用すると、順序付けされていないルート化されていない (0 ノードのない) バージョンから、順序付けられたバージョンと 0 ベースをcalculateDeepLevel計算できます。dbdb
最初にいくつかのインポート、
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
StackOverflow で得られる回答の質は、提供する質問の質にほぼ完全に依存します。コードを含む回答が必要な場合は、質問にコードを入力する必要があります。特定のライブラリに関する回答が必要な場合は、それを参照してください。
Data.Map現在、あなたの質問は非常に漠然としています。私が答えることができるのは、最初に中間結果を蓄積し、この中間データ構造を照会して再配置するのに似た構造を使用する必要があるということだけです。ドキュメントが示すように、ほとんどのアクセサ関数の複雑さO(log n)は非常に効率的です。
問題が具体的すぎるため、どのデータベースライブラリにもそのような機能を期待するべきではありません。