[Haskell-beginners] about the concatenation on a tree

[Thomas Davie]

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