将树转换为功能图库树的优雅方法？

我的问题涉及将树转换为Functional Graph Library表示时出现的显而易见的尴尬，它需要显式引用节点名称才能插入更多节点/边。将树转换为功能图库树的优雅方法？

具体来说，我递归地构建了一棵玫瑰树（目前Data.Tree.Tree a from containers），并且想将它转换为Gr 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()（使用秒差距）与单子变压器一个简单的应用性的解析器，只要它需要解析器微创变化。）

来源

2012-11-13 Fixnum

可以使用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-31 09:02:16 pat

将树转换为功能图库树的优雅方法？

回答

相关问题