On 10/04/12 09:55, Arnaud Bailly wrote:
Hello,
I am manipulating labeled multiway trees, some kind of "lightweight"
XML notation. One thing I would like to be able to do is manipulating
a tree as a list of (Path, Value). Generating such a list is easy but
I am a little bit surprised to find it harder to reconstruct a tree,
given such a list assuming some sensible properties (list is ordered,
for example).
I got the intuition this has already been tackled in one way or
another in a functional setting in Haskell (I code in Java but using
mostly functional constructs), but don't know where to look.
The haskell solution would be to consider first how to turn a single
(Path,Value) into a tree. Then you just combine these trees for all the
paths by taking their union. I attached some code.
Twan
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"
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
