Defining fmap for a binary search tree

Question

I'm working through the exercises in the book "Beginning Haskell." Exercise 4-8 is to make a binary search tree an instance of Functor and define fmap. This is what the tree looks like:

data BinaryTree a = Node a (BinaryTree a) (BinaryTree a) 
                  | Leaf
                    deriving Show

Because it is a search tree, all operations on the tree must maintain the invariant that all values in the left subtree are < the node's value and all values in the right subtree are > the node's value. This means that all values in the tree must be ordinal (Ord a => BinaryTree a).

Two questions:

1. Since fmap :: (a -> b) -> BinaryTree a -> BinaryTree b, how do I enforce that b is also ordinal? If it didn't have to be a Functor, I could simply do fmapOrd :: (Ord a, Ord b) => (a -> b) -> BinaryTree a -> BinaryTree b, but the Functor typeclass doesn't enforce the Ord contraints.
2. What does an efficient implementation look like? My first thought was to fold over the tree, and build up a new tree out of the mapped values. Unfortunately, I didn't get this far because of (1).

Answer 1

If you want to enforce ordering, then your binary tree as it is cannot be made into a functor, because - as you pointed out - the types don't match. However, while the tree can't be a functor over the keys, it can be a functor over the values, provided that there are separate type parameters for each. The standard Data.Map (also implemented as a search tree) works this way.

-- Now the "v" parameter can be mapped over without any care for tree invariants
data Tree k v = Node k v (Tree k v) (Tree k v) | Leaf 

As to the implementation of fmap, your first thought is right. There is also a lazier way though, namely letting GHC derive the instance:

{-# LANGUAGE DeriveFunctor #-}

data Tree k v = Node k v (Tree k v) (Tree k v) | Leaf deriving (Functor)

It pretty much always matches your intents, just remember to let the last type parameter be the one you intend to map over.

Answer 2

The point of Functors and fmap is that it works for all a and b that can be stored in your data structure, just like Monad has to work for all types a as well. Your Functor instance should look like

instance Functor BinaryTree where
    fmap f Leaf = Leaf
    fmap f (Node a l r) = Node (f a) (fmap f l) (fmap f r)

But if you then want to ensure that mapping over a binary tree keeps it balanced, then you need a function

balanceTree :: Ord a => BinaryTree a -> BinaryTree a

You should be able to implement this function fairly easily with some googling, then you can define a specialized mapping function

binMap :: (Ord a, Ord b) => (a -> b) -> BinaryTree a -> BinaryTree b
binMap f = balanceTree . fmap f

And then you should ensure that you and the users of your library never use fmap (unless necessary) and instead use binMap.