[Haskell-cafe] A binary tree
Sven.Panne at aedion.de
Sun Jul 4 10:22:17 EDT 2004
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))
More information about the Haskell-Cafe