[Haskell-cafe] A binary tree

[Sven Panne]

paolo veronelli wrote:
> I want to build a binary tree where each leaf is a string of "L" and "R" 
> defining their position from the top
> 
> This should be done without context isn't it?

I'm not sure what you mean with "context" here, but anyway...

> data Tree a = Fork (Tree a) (Tree a) | Leaf a deriving Show
> 
> t =Leaf ""
> 
> treeGrower :: Tree a -> Tree a
> treeGrower (Leaf a )= treeGrower (Fork (Leaf (a++"1")) (Leaf (a++"2")))
> treeGrower (Fork l r)  = Fork (treeGrower l) (treeGrower r)
> 
> ghci says:
>     Cannot unify the type-signature variable `a' with the type `[a1]'
>         Expected type: [a1]
>         Inferred type: a
>     In the first argument of `(++)', namely `a'
>     In the first argument of `Leaf', namely `(a ++ "1")'
> 
> I don't get it.........

That means that the type for treeGrower is wrong: Because (++) is used with
the elements contained in the leaves, these elements must be of a list type
(i.e. [a1]). But the type signature pretends that treeGrower could be applied
to trees with any kind of leaf elements (i.e. a). But even

    treeGrower :: Tree [a1] -> Tree a

would be too general, as GHC would have found out. Strings are appended to the
leaf elements, so the correct type would be

    treeGrower :: Tree String -> Tree a

Even without looking at any code, this should give you an uneasy feeling.
It essentially says: You have to give me a tree, and I will return a tree
with leaf elements of any kind you want!? This is a strong hint that treeGrower
will not have a finite value, try it for yourselves.

To achieve what you want, construct the (reverse) path while descending the
tree and plumb it into any leaf encountered:

    labelTree :: Tree a -> Tree String
    labelTree tree = label tree ""
       where label (Leaf _)   path = Leaf (reverse path)
             label (Fork l r) path = Fork (label l ('l':path)) (label r ('r':path))

Cheers,
    S.