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

Question

我的问题涉及将树转换为功能图库表示的明显尴尬,该表示需要显式引用节点名称以插入更多节点/边.

具体来说,我递归构建玫瑰树(目前Data.Tree.Tree a从containers),并希望将其转换为一个Gr a ()调用各种功能反对.为此,可以首先遍历树(使用供应monad或其中一个FGL的状态monad类型,如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变换器生成,前提是它需要对解析器进行微创更改.)

Answer 1

您可以使用 aWriter来收集要传递给 的节点列表和边列表mkGraph。使用列表 withWriter效率不高，因此我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