<br><div class="gmail_quote">On Wed, May 7, 2008 at 6:28 AM, patrik osgnach <<a href="mailto:patrik.osgnach@gmail.com">patrik.osgnach@gmail.com</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Daniel Fischer ha scritto:<div><div></div><div class="Wj3C7c"><br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Am Dienstag, 6. Mai 2008 22:40 schrieb patrik osgnach:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Brent Yorgey ha scritto:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
On Tue, May 6, 2008 at 8:20 AM, patrik osgnach <<a href="mailto:patrik.osgnach@gmail.com" target="_blank">patrik.osgnach@gmail.com</a>><br>
<br>
wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hi. I'm learning haskell but i'm stuck on a generic tree folding<br>
exercise. i must write a function of this type<br>
treefoldr::(Eq a,Show a)=>(a->b->c)->c->(c->b->b)->b->Tree a->c<br>
Tree has type<br>
data (Eq a,Show a)=>Tree a=Void | Node a [Tree a] deriving (Eq,Show)<br>
as an example treefoldr (:) [] (++) [] (Node '+' [Node '*' [Node 'x' [],<br>
Node 'y' []], Node 'z' []])<br>
must return "+∗xyz"<br>
any help?<br>
(sorry for my bad english)<br>
</blockquote>
Having a (Tree a) parameter, where Tree is defined as an algebraic data<br>
type, also immediately suggests that you should do some pattern-matching<br>
to break treefoldr down into cases:<br>
<br>
treefoldr f y g z Void = ?<br>
treefoldr f y g z (Node x t) = ?<br>
<br>
-Brent<br>
</blockquote>
so far i have tried<br>
treefoldr f x g y Void = x<br>
</blockquote>
<br>
Yes, nothing else could be done.<br>
<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
treefoldr f x g y (Node a []) = f a y<br>
</blockquote>
<br>
Not bad. But actually there's no need to treat nodes with and without children differently.<br>
Let's see:<br>
<br>
treefoldr f x g y (Node v ts)<br>
<br>
should have type c, and it should use v. We have<br>
f :: a -> b -> c<br>
x :: c<br>
g :: c -> b -> b<br>
y :: b<br>
v :: a.<br>
<br>
The only thing which produces a value of type c using a value of type a is f, so we must have<br>
<br>
treefoldr f x g y (Node v ts) = f v someExpressionUsing'ts'<br>
<br>
where<br>
<br>
someExpressionUsing'ts' :: b.<br>
<br>
The only thing we have which produces a value of type b is g, so<br>
someExpressionUsing'ts' must ultimately be g something somethingElse.<br>
Now take a look at the code and type of foldr, that might give you the idea.<br>
<br>
Cheers,<br>
Daniel<br>
<br>
<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
treefoldr f x g y (Node a (t:ts)) = treefoldr f x g (g (treefoldr f x g<br>
y t) y) (Node a ts)<br>
but it is incorrect. i can't figure out how to build the recursive call<br>
thanks for the answer<br>
Patrik<br>
</blockquote>
<br>
<br>
</blockquote></div></div>
thanks for the tip.<br>
so, if i have understood correctly i have to wirite something like:<br>
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 ...<br>
it looks like a list foldr so...<div class="Ih2E3d"><br>
treefoldr f x g y Void = x<br></div>
treefoldr f x g y (Node a ts) = f a (foldr (g) y (map (treefoldr f x g y) ts))<br>
it seems to work. i'm not yet sure it is correct but is better than nothing<br>
thanks to you all. now i will try to write a treefoldl<div><div></div><div class="Wj3C7c"></div></div></blockquote><div><br><br>If it typechecks and you have used all the parameters, then it is probably correct! =) That may sound trite, but it is often true. <br>
<br>-Brent<br><br></div></div>