5

私の質問は、ツリーをそのFunctional Graph Library表現に変換する際の明らかな厄介さに関するものです。これには、さらにノード/エッジを挿入するためにノード名を明示的に参照する必要があります。

Data.Tree.Tree a具体的には、ローズ ツリー (現在はfrom )を再帰的に構築し、それを に変換して、それに対してさまざまな関数を呼び出しcontainersたいと考えています。Gr a ()そのためには、まずツリーを (供給モナドまたは NodeMapM のような FGL の状態モナド型の 1 つを使用して) たどり、各ノードに識別子をタグ付けします。

{-# LANGUAGE TupleSections #-}
import Control.Monad.Supply
import Data.Graph.Inductive
import Data.Tree

tagTree :: Tree a -> Supply Int (Tree (a,Int))
tagTree (Node n xs) = do
  xs' <- sequence (map tagTree xs)
  s   <- supply
  return $ Node (n,s) xs'

そしてevalSupply (tagTree tree) [1..]、次のようなものを使用します

taggedTreeToGraph :: Tree (a,Int) -> Gr a ()
taggedTreeToGraph (Node (n,i) xs) =
  ([],i,n,map (((),) . snd . rootLabel) xs)
    & foldr graphUnion empty (map taggedTreeToGraph xs)
      where
        graphUnion = undefined -- see 'mergeTwoGraphs' in package 'gbu'

もちろん、これらの 2 つの段階を組み合わせることができます。

それで、これはこの変換を行う良い方法ですか？または、私が見逃しているより簡単な方法、または (できれば非常に一般的な) ツリーのようなデータ構造を FGL ツリーに変換するために使用する必要がある抽象化がありますか?

編集: この質問のポイントは、元のパーサーが 4 行しかなく、 のような非常に単純なコンビネーターを使用していることだと思いますliftA (flip Node [])が、返された表現を変更するには、上記の大きなコードが必要なようです。これは奇妙です。

Gr a ()(パーサーへの最小限の侵襲的変更が必要であるという条件で、モナド変換子を使用してパーサー (Parsec を使用した単純なアプリケーション パーサー) から直接生成できれば幸いです。)

4

1 に答える 1

3

を使用しWriterて、 に渡すノードのリストとエッジのリストを収集できますmkGraph。でリストを使用するのWriterは効率的ではないため、DList代わりに使用し、最後にリストに変換します。

import Data.Tree
import Data.Graph.Inductive
import Data.DList (singleton, fromList, toList)
import Control.Monad.RWS
import Control.Arrow

treeToGraph :: Tree a -> Gr a ()
treeToGraph t = uncurry mkGraph . (toList *** toList) . snd $ evalRWS (go t) () [1..]
  where go (Node a ns) = do
          i <- state $ head &&& tail
          es <- forM ns $ go >=> \j -> return (i, j, ())
          tell (singleton (i, a), fromList es)
          return i
于 2013-01-31T09:02:16.393 に答える