haskell - 将树转换为函数图库树的优雅方法？

Question

我的问题涉及将一棵树转换为它的 Functional Graph Library 时明显的尴尬。表示，需要显式引用节点名称才能插入更多节点/边。

具体来说，我已经递归地构建了一棵玫瑰树(当前是来自 containers 的 Data.Tree.Tree a)，并希望将其转换为 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树)[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 [])，但似乎要更改返回的表示需要上面的大代码，这很奇怪。

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

Answer 1

您可以使用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