On 31 Dec 2008, at 16:02, Max cs wrote:
hi all, not sure if there is someone still working during holiday
like me : )
I got a little problem in implementing some operations on tree.
suppose we have a tree date type defined:
data Tree a = Leaf a | Branch (Tree a) (Tree a)
I want to do a concatenation on these tree just like the concat on
list.
Anyone has idea on it? or there are some existing implementation?
Thank you and Happy New Year!
How would you like to concatenate them? Concatonation on lists is
easy because there's only one end point to attach the next list to, on
a tree though, there are many leaves to attach things to.
Here's a few examples though:
Attaching to the right most point on the tree (tree data structure
modified to store data in branches not leaves here)
data Tree a = Leaf | Branch (Tree a) a (Tree a)
concatT :: [Tree a] -> Tree a
concatT = foldr1 appendT
appendT :: Tree a -> Tree a -> Tree a
appendT Leaf t = t
appendT (Branch l x r) t = Branch l x (appendT r t)
Attaching to *all* the leaves on the tree (same modification to the
data structure)
concatT :: [Tree a] -> Tree a
concatT = foldr1 appendT
appendT :: Tree a -> Tree a -> Tree a
appendT Leaf t = t
appendT (Branch l x r) t = Branch (appendT l t) x (appendT r t)
merging a list of trees maintaining them as ordered binary trees
concatT :: Ord a => [Tree a] -> Tree a
concatT = foldr1 unionT
unionT :: Ord a => Tree a -> Tree a -> Tree a
unionT t = foldrT insertT t
foldrT :: (a -> b -> b) -> b -> Tree a -> b
foldrT f z Leaf = z
foldrT f z (Branch l x r) = f x (foldrT f (foldrT f z r) l)
insertT :: Ord a => a -> Tree a -> Tree a
insertT x Leaf = Branch Leaf x Leaf
insertT x (Branch l y r)
| x <= y = Branch (insertT x l) y r
| otherwise = Branch l y (insertT x r)
Hope that helps.
Bob
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
