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