Haskell functor for red-black tree

Question

So I'm learning Haskell and I have a red-black tree with different types in red and black nodes implemented like this:

data Rbtree a1 b1 = EmptyTree | Node a1 (Rbtree b1 a1) (Rbtree b1 a1) deriving (Show, Read, Eq)

And now I need to define a functor instance for it. Because Rbtree is a type constructor that takes two parameters I have to make an instance for Rbtree c. And after this I'm stuck. My code now is something like this:

instance Functor (Rbtree c) where
fmap f EmptyTree = EmptyTree
fmap f (Node x left right) = Node x (fmap f left) (fmap f right)

As you could guess that does't compile. (compilation errors). I understand that fmap for it has to be (a -> b) -> (Rbtree c) a -> (Rbtree c) b and looking deeper for Node part it has to be (a -> b) -> (Node c (Rbtree a c) (Rbree a c)) -> (Node c (Rbtree b c) (Rbree b c)). What I do not understand is how to unfold left and right so i can apply f only to part of it. I think I'm missing something here.

Answer 1

instance Functor (Rbtree c) where
  fmap = fmap_even where
     fmap_even _ EmptyTree = EmptyTree
     fmap_even f (Node x left right) = Node x (fmap_odd f left) (fmap_odd f right)
     fmap_odd  _ EmptyTree = EmptyTree
     fmap_odd  f (Node x left right) = Node (f x) (fmap_even f left) (fmap_even f right)

Your definition of RB tree doesn't make much sense to me, but in case i'm missing something, here's a Functor instance that is compatible with it.