```Daniel Fischer ha scritto: ``````Am Dienstag, 6. Mai 2008 22:40 schrieb patrik osgnach: ``````Brent Yorgey ha scritto: ``````On Tue, May 6, 2008 at 8:20 AM, patrik osgnach 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) ``````Having a (Tree a) parameter, where Tree is defined as an algebraic data type, also immediately suggests that you should do some pattern-matching to break treefoldr down into cases: treefoldr f y g z Void = ? treefoldr f y g z (Node x t) = ? -Brent ``````so far i have tried treefoldr f x g y Void = x `````` Yes, nothing else could be done. ``````treefoldr f x g y (Node a []) = f a y `````` ```Not bad. But actually there's no need to treat nodes with and without children differently. ```Let's see: treefoldr f x g y (Node v ts) should have type c, and it should use v. We have f :: a -> b -> c x :: c g :: c -> b -> b y :: b v :: a. ```The only thing which produces a value of type c using a value of type a is f, so we must have ``` treefoldr f x g y (Node v ts) = f v someExpressionUsing'ts' where someExpressionUsing'ts' :: b. The only thing we have which produces a value of type b is g, so ```someExpressionUsing'ts' must ultimately be g something somethingElse. ```Now take a look at the code and type of foldr, that might give you the idea. Cheers, Daniel ``````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 incorrect. i can't figure out how to build the recursive call thanks for the answer Patrik `````` ``````thanks for the tip. so, if i have understood correctly i have to wirite something like: ```treefoldr f x g y (Node a ts) = f a (g (treefoldr f x g y (head ts)) (g (treefoldr f x g y (head (tail ts)) (g ... ```it looks like a list foldr so... treefoldr f x g y Void = x ```treefoldr f x g y (Node a ts) = f a (foldr (g) y (map (treefoldr f x g y) ts)) ```it seems to work. i'm not yet sure it is correct but is better than nothing thanks to you all. now i will try to write a treefoldl _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@xxxxxxxxxxx http://www.haskell.org/mailman/listinfo/haskell-cafe ```