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.
_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
