title: Defining fmap for a binary search tree
body: <p>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:</p>
  
  <pre><code>data BinaryTree a = Node a (BinaryTree a) (BinaryTree a) 
                    | Leaf
                      deriving Show
  </code></pre>
  
  <p>Because it is a search tree, all operations on the tree must maintain the invariant that all values in the left subtree are &lt; 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 (<code>Ord a =&gt; BinaryTree a</code>).</p>
  
  <p>Two questions:</p>
  
  <ol>
  <li>Since <code>fmap :: (a -&gt; b) -&gt; BinaryTree a -&gt; BinaryTree b</code>, how do I enforce that <code>b</code> is also ordinal? If it didn't have to be a Functor, I could simply do <code>fmapOrd :: (Ord a, Ord b) =&gt; (a -&gt; b) -&gt; BinaryTree a -&gt; BinaryTree b</code>, but the Functor typeclass doesn't enforce the Ord contraints.</li>
  <li>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).</li>
  </ol>