Haskell - Elegant way to convert a tree to a Functional Graph Library tree

Questions

http://hackage.haskell.org/package/fgl-5.4.2.4 http://hackage.haskell.org/package/fgl-5.4.2.4

Specifically, I ve recursively built a rose tree (currently a Data.Tree.Tree a from containers), and want to convert it to a Gr a () to call various functions against it. To do so, one can first walk the tree (with the supply monad or one of the FGL s state monad types like NodeMapM) and tag each node with an identifier:

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

and then evalSupply (tagTree tree) [1..], then use something like

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 

Of course, these two stages can be combined.

So, is this a good way to do this conversion? Or is there a simpler way I m missing, or an abstraction I should be using of the conversion of a (hopefully very generic) tree-like data structure to an FGL tree?

Edit: I guess the point of this question is that my original parser is only four lines long and uses very simple combinators like liftA (flip Node []), but to change the returned representation seemingly requires the large code above, which is strange.

(I d be happy to produce a Gr a () directly from the parser (a simple applicative parser using Parsec) with monad transformers, provided that it required minimally invasive changes to the parser.)

Answers

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

Source

License : cc by-sa 3.0

http://stackoverflow.com/questions/13355968/elegant-way-to-convert-a-tree-to-a-functional-graph-library-tree

Related