트리를 기능 그래프 라이브러리 트리로 변환하는 우아한 방법?

Question

제 질문은 트리를 Functional Graph Library 표현으로 변환하는 데있어서 명백한 어색함에 관한 것입니다.이 표현은 추가 노드/에지를 삽입하기 위해 명시 적으로 노드 이름을 참조해야합니다.

특히 장미 나무 (현재는 Data.Tree.Tree a에서 containers까지)를 재귀 적으로 작성했으며이를 다양한 기능을 호출하기 위해 Gr a()으로 변환하려고합니다. 이렇게하려면, 하나는 첫 번째 (공급 모나드 또는 NodeMapM 같은 FGL의 상태 모나드의 종류 중 하나) 트리를 걸어 식별자로 각 노드를 태그 할 수 있습니다

{-# 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 트리의 변환 중 사용해야하는 추상화?

편집 :이 질문의 요점은 내 원래 파서는 길이가 4 줄이고 liftA (flip Node [])과 같은 매우 간단한 연결자를 사용하지만 반환 된 표현을 변경하려면 위의 큰 코드가 필요하다는 것입니다.

(나는 그것이 파서 최소 침습 변경 필요하다는 제공 (파서에서 직접 모나드 변압기와 파섹)를 사용하여 간단한 실용적 파서를 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