[Haskell-beginners] about the concatenation on a tree
Thomas Davie
tom.davie at gmail.com
Wed Dec 31 11:30:30 EST 2008
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
More information about the Beginners
mailing list