On Wed, May 7, 2008 at 6:28 AM, patrik osgnach <[EMAIL PROTECTED]> wrote:
> 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 < >>>> [EMAIL PROTECTED]> >>>> >>>> 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 > If it typechecks and you have used all the parameters, then it is probably correct! =) That may sound trite, but it is often true. -Brent
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe