[Haskell-cafe] help in tree folding

[patrik osgnach]

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 <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)
>>> 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