about the concatenation on a tree

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

about the concatenation on a tree

Max cs
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!

regards,
Max
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20081231/8de41a30/attachment.htm
Reply | Threaded
Open this post in threaded view
|

about the concatenation on a tree

Max cs
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!

regards,
Max
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20081231/20794b50/attachment.htm
Reply | Threaded
Open this post in threaded view
|

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
Reply | Threaded
Open this post in threaded view
|

Re: about the concatenation on a tree

Thomas Davie

On 31 Dec 2008, at 22:38, Max.cs wrote:

> Hi Bob,
>
> Actually I am a fresher in the university and I am doing a  
> additional exercise for the holiday.
>
> I think your modification is great, but I am afraid I have to keep  
> the original forms of the function and data type. I am given the  
> following code:
>
>> data Tree a = Leaf a | Branch (Tree a) (Tree a)
>
>> foldTree :: (a -> b) -> (b -> b -> b) -> Tree a -> b
>> foldTree f g (Leaf x) = f x
>> foldTree f g (Branch t1 t2) = g (foldTree f g t1) (foldTree f g t2)
>
> now, what I am asked to do is to complete the following function  
> concatT using the above foldTree.
>
>> concatT :: Tree (Tree a) -> Tree a
>
> the example output of concatT are also given as:
>
> concatT (Leaf t) = t
> concatT (Branch (Leaf t1) (Leaf t2)) = Branch t1 t2
>
> I am confused by the type of function concatT and foldTree:
>
> From the output example, we know, the output should be t (atomic  
> value) when the input is (Leaf t), and the output will be Branch t1  
> t2 (a Branch) when the input is a Branch. But the the definition of  
> foldTree, the return type of f and g should be the same (both are  
> b). Am I missing some important point? Any idea on how we can  
> implement the function concatT ?

Sure, but lets go through (most of) the process.  We know the function  
we need has the type Tree (Tree c) -> Tree c.  You'll see why I used c  
as my variable in a minute, and we're given a function with the type  
(a -> b) -> (b -> b -> b) -> Tree a -> b.  Lets try and make that into  
the type we need.  We know the result type must be "Tree c", so lets  
try replacing all bs with Tree cs:

someFunction :: (a -> Tree c) -> (Tree c -> Tree c -> Tree c) -> Tree  
a -> Tree c

We also know that the argument type we want is not a Tree of any  
values, but actually a Tree of Tree cs, so lets supstitute a for Tree  
c too:

someOtherFunction :: (Tree c -> Tree c) -> (Tree c -> Tree c -> Tree  
c) -> Tree (Tree c) -> Tree c

As we know, in Haskell functions are curried, so this type is the same  
as (Tree c -> Tree c) -> ((Tree c -> Tree c -> Tree c) -> (Tree (Tree  
c) -> Tree c)).  Note that the last part here is exactly the type we  
need, so if we provide foldTree with the right two functions, it looks  
like it's gonna do exactly what we want.  Lets look at the rules for  
foldTree ? it applies f wherever it meets a Leaf, and g wherever it  
meets a Branch, so lets think about what we want to do in those two  
situations.

In the case of a Leaf, we'd like to replace the leaf with it's value,  
so the function we're looking for sounds a lot like it does nothing  
much.

In the case of Branches, we'd like to leave them in place, so we  
probably want to look at the Branch creator function.

I'll leave the rest to you :)

> Btw, it will be much better if you do not send this email and the  
> replies to the maillist for this instance, since I think it is not a  
> very good idea to let my tutor know I am asking question involved in  
> the exercise. Just let me know if you dont know you want to answer  
> this question : )

I'm sure your tutor doesn't mind you asking for help, in fact, he's  
probably the first guy you should go and ask for some help.  What he  
will want to know is exactly how much help you're getting, and how  
you're doing with the subject matter ? remember, he's trying to teach  
you, not trying to torture you :).  Because of that, I have forwarded  
this email to the mailing list, you're welcome to use my help or not,  
depending on how guilty you feel (although unless this is a test, any  
guilt you feel is entirely in error).

Bob
Reply | Threaded
Open this post in threaded view
|

Re: about the concatenation on a tree

Thomas Davie
>
> hi Bob,
>
> I believe the type of foldTree is implementable, but what confuses  
> me is
>
> the output example:
>
>> concatT (Leaf t) = t
>> concatT (Branch (Leaf t1) (Leaf t2)) = Branch t1 t2
>
> they seem to be inconsistent with the type of concatT which return a  
> Tree only, but in the Leaf case, a atomic value is returned?
>
> anything important I am missing?

You need to remember what type is stored in that Leaf ? remember that  
this is a Tree (Tree a) ? i.e. the variable t in the line above has  
the type Tree a.

Bob
Reply | Threaded
Open this post in threaded view
|

Re: about the concatenation on a tree

Achim Schneider
In reply to this post by Max cs
"Max cs" <[hidden email]> 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?
>
The semantics of tree concat vary, depending on what type of tree you
want to have. In the simplest case, it's unbalanced, so you can just do

concat :: Tree a -> Tree a -> Tree a
concat x y = Branch x y

if, on the other hand, you want to keep the tree balanced, or sorted,
or whatever, things get more involved.

--
(c) this sig last receiving data processing entity. Inspect headers
for copyright history. All rights reserved. Copying, hiring, renting,
performance and/or quoting of this signature prohibited.