Is it possible to create a Functor instance for sorted binary trees in Haskell?
design-patterns, functional-programming, functor, haskell
Solution
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 `Functor`s (`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 `Set`s 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 `SortBinTree`s over types with an `Ord` instance. (Modulo some potential concerns about "uncooperative" `Eq`/`Ord` instances like those that mess with `Set` being a `Functor`.)
Problem
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?