import qualified Data.Map as Map
import Data.Map (Map)
data Tree a b = Leaf b | Branch (Map a (Tree a b))
type Path a = [a]
fromTree :: Tree a b -> [(Path a,b)]
fromTree (Leaf x) = [([],x)]
fromTree (Branch xs) = [ (a:p,x) | (a,t) <- Map.toList xs, (p,x) <- fromTree t ]
toTree :: Ord a => [(Path a,b)] -> Tree a b
toTree = foldr unionTree emptyTree . map (uncurry toTree1)
toTree1 :: Ord a => Path a -> b -> Tree a b
toTree1 [] b = Leaf b
toTree1 (x:xs) b = Branch (Map.singleton x (toTree1 xs b))
emptyTree :: Tree a b
emptyTree = Branch Map.empty
unionTree :: Ord a => Tree a b -> Tree a b -> Tree a b
unionTree (Branch xs) y | Map.null xs = y
unionTree x (Branch ys) | Map.null ys = x
unionTree (Branch xs) (Branch ys) = Branch (Map.unionWith unionTree xs ys)
unionTree _ _ = error "Can't have a leaf on the same level as something else"