I am having trouble getting my code to do a preorder traversal of a tree to a list to work. The definition for the tree is as follows:
data Tree a b = Branch b (Tree a b) (Tree a b)
| Leaf a
and my definition for preorder traversal is as follows:
preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c]
preorder f g (Leaf b) = [g b]
preorder f g (Branch a left right) = [f a] ++ preorder f g left ++ preorder f g right
However the error I am getting is:
Couldn't match type `b' with `a'
`b' is a rigid type variable bound by
the type signature for
preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c]
`a' is a rigid type variable bound by
the type signature for
preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c]
In the first argument of `f', namely `a'
In the expression: f a
In the first argument of `(++)', namely `[f a]'
I know my problem is the type of the first argument of that function and how it needs to be of type [c] but I cannot figure out for the life of me how to get that. I have tried all combinations of brackets around the f a and no brackets and none give me a successful run.
You've got your types or function calls mixed up - probably the types, given the way you've named your variables.
You've said that Tree a b has a b in its first argument, but the f argument to preorder takes an a. Similarly Leaf takes an a but you're calling g on it, which takes a b.
That's what the error message is telling you: the first argument you passed to f is of type b, when it expected an a.
If you change your datatype to:
data Tree a b = Branch a (Tree a b) (Tree a b)
| Leaf b
Then your code compiles fine.
Alternatively change preorder to
preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c]
preorder f g (Leaf a) = [f a]
preorder f g (Branch b left right) = [g b] ++ preorder f g left ++ preorder f g right