Haskell - Tree traversal: preorder

Question

I am fairly new to Haskell, and is trying to work on an assignment from my class. I am trying to create a preorder function to traverse through a tree object in the following format

preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c]
preorder f g Empty = []
preorder f g (Leaf x) = [x]

My Tree class is as following

data Tree a b = Empty | Leaf b | Branch a (Tree a b) (Tree a b)

When defining the preorder function, I get errors as shown below.

Couldn't match expected type 'c' with actual type 'b'
'c' is a rigid type variable bound by the type signature for preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c].
'b' is a rigid type variable bound by the type signature for preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c].

And they occurred at the last preorder function definition

preorder f g (Leaf x) = [x]

Answer 1

The type Tree a b contains leaves with elements of type b and branches with elements of type a in addition to empty leaves. You wish to visit each node of the tree in preorder, collecting the results of applying the functions f :: a -> c and g :: b -> c in a list of type [c]. The reason that the compiler complains about your preorder function is that x has type b; this forces c to unify with b. But this is a less general type than you have indicated to the compiler. As an exercise, see if you can write a more specific type for your function that the compiler accepts. Hint: are b and c distinct types?

However, you are given a function g :: b -> c. Applying this function to x yields a value of type c, and this value can be collected into a list of type [c]. This list may or may not contain elements of type a or b. You can rewrite the preorder traversal in accord with the given signature in the following way:

preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c]
preorder f g Empty          = []
preorder f g (Leaf b)       = [g b]
preorder f g (Branch a l r) = f a : preorder f g l ++ preorder f g r