[Haskell-cafe] help in tree folding

[patrik osgnach]

Luke Palmer ha scritto:
> On Tue, May 6, 2008 at 6:20 AM, patrik osgnach <patrik.osgnach at gmail.com> wrote:
>> Hi. I'm learning haskell but i'm stuck on a generic tree folding exercise. i
>> must write a function of this type
>>  treefoldr::(Eq a,Show a)=>(a->b->c)->c->(c->b->b)->b->Tree a->c
>>  Tree has type
>>  data (Eq a,Show a)=>Tree a=Void | Node a [Tree a] deriving (Eq,Show)
>>  as an example treefoldr (:) [] (++) [] (Node '+' [Node '*' [Node 'x' [],
>> Node 'y' []], Node 'z' []])
>>  must return "+∗xyz"
>>  any help?
>>  (sorry for my bad english)
> 
> Functions like this are very abstract, but are also quite nice in that
> there's basically only one way to write them given the types.
> 
> What have you tried so far?  This function needs to be recursive, so
> what arguments should it give to its recursive calls, and where should
> it plug the results?
> 
> It also helps, as you're writing, to keep meticulous track of the the
> types of everything you have and the type you need, and that will tell
> you what you need to write next.
> 
> Luke
so far i have tried this
treefoldr f x g y Void = x
treefoldr f x g y (Node a []) = f a y
treefoldr f x g y (Node a (t:ts)) = treefoldr f x g (g (treefoldr f x g 
y t) y) (Node a ts)
but it is clearly incorrect. this functions takes as arguments two 
functions and two zeros (one for the empty tree and one for the empty 
tree list). thanks for the answer
Patrik