Is it possible to create a Functor instance for sorted binary trees in Haskell?

Question

Imagine we have a SortBinTree type constructor defined as, for example,

data SortBinTree a = EmptyNode | Node a (SortBinTree a) (SortBinTree a);

It make sense only when a is an instance of Ord type class, so most functions have :: (Ord a) => in the beginning of their declaration, especially a function for creating such a tree from list. However to teach Haskell, that SortBinTree is an instance of Functor type class we have to write something like

instance Functor SortBinTree where
  fmap g tree = ...

The problem here is that we have to deal with g :: a->b, where b is not necessarily an instance of Ord type class. That makes it problematic to write such function, since we can't use inequalities while creating an element of the type SortBinTree b.

Is there a standard workaround here? Any way to define fmap only for the case b is in Ord type class?

Answer 1

No, there's no way to do this with the Functor type class. As you noted, the Prelude gives us¹

class Functor f where
  fmap :: (a -> b) -> f a -> f b

which provides no way to hang a restriction on the b. We can define an OrdFunctor class:

class OrdFunctor f where
  fmapOrd :: (Ord a, Ord b) => (a -> b) -> f a -> f b

This might get annoying if we had lots of different kinds of Functors (EqFunctor, MonoidFunctor, etc.) But if we turn on ConstraintKinds and TypeFamilies, we can generalize this to a restricted functor class:

{-# LANGUAGE ConstraintKinds, TypeFamilies #-}
import GHC.Exts (Constraint)
import Data.Set (Set)
import qualified Data.Set as S

class RFunctor f where
  type RFunctorConstraint f :: * -> Constraint
  fmapR :: (RFunctorConstraint f a, RFunctorConstraint f b) => (a -> b) -> f a -> f b

-- Modulo the issues with unusual `Eq` and `Ord` instances, we might have
instance RFunctor Set where
  type RFunctorConstraint f = Ord
  fmapR = S.map

(Often, you'll see stuff about restricted monads; it's the same idea.)

Or, as jozefg suggested, you could just write your own treeMap function and not put it in a type class. Nothing wrong with that.

Note, however, that you should be careful when making SortBinTree a functor; the following is not fmap. (It is, however, what deriving (..., Functor) will produce, so don't use that.)

notFmap :: (Ord a, Ord b) => (a -> b) -> SortBinTree a -> SortBinTree b
notFmap f EmptyNode    = EmptyNode
notFmap f (Node x l r) = Node (f x) (notFmap l) (notFmap r)

Why not? Consider notFmap negate (Node 2 (Node 1 EmptyNode EmptyNode) EmptyNode). That will produce the tree Node (-2) (Node (-1) EmptyNode EmptyNode) EmptyNode), which presumably violates your invariants – it's sorted backwards.² So make sure your fmap is invariant-preserving. Data.Set splits these into map, which makes sure the invariants are preserved, and mapMonotonic, which requires you to pass in an order-preserving function. This latter function has the simple implementation, à la notFmap, but could produce invalid Sets if given uncooperative functions.

---

¹ The Data.Functor module also exposes the (<$) :: Functor f => a -> f b -> a type class method, but that's just there in case fmap . const has a faster implementation.

² However, notFmap is fmap from the subcategory of Hask whose objects are types with an Ord instance and whose morphisms are order-preserving maps to a subcategory of Hask whose objects are SortBinTrees over types with an Ord instance. (Modulo some potential concerns about "uncooperative" Eq/Ord instances like those that mess with Set being a Functor.)