[Haskell-cafe] help in tree folding

[Daniel Fischer]

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