5

我的问题涉及将树转换为其功能图形库表示形式的明显笨拙，这需要显式引用节点名称才能插入更多节点/边。

具体来说，我递归地构建了一棵玫瑰树（目前是 a Data.Tree.Tree afrom containers），并希望将其转换为 aGr a ()以针对它调用各种函数。为此，可以首先遍历树（使用供应单子或 FGL 的状态单子类型之一，如 NodeMapM）并用标识符标记每个节点：

{-# 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'

当然，这两个阶段可以合并。

那么，这是进行这种转换的好方法吗？或者是否有一种我遗漏的更简单的方法，或者我应该使用将（希望非常通用的）树状数据结构转换为 FGL 树的抽象？

编辑：我想这个问题的重点是我的原始解析器只有四行长，并且使用了非常简单的组合器，例如liftA (flip Node [])，但是要更改返回的表示似乎需要上面的大代码，这很奇怪。

（我很乐意Gr a ()直接从解析器（使用 Parsec 的简单应用解析器）和 monad 转换器生成一个，前提是它需要对解析器进行微创更改。）

4

1 回答 1

3

You can use a Writer to collect the list of nodes and the list of edges to pass to mkGraph. Using lists with Writer is not efficient, so I'm using DList instead, and converting back to lists at the end.

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 回答