CODEWITHSUNDEEP
design-patternshaskellfunctional-programmingfunctor
fiktor
fiktor

Reputation: 1413

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

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?

Upvotes: 6

Views: 1021

Answers (2)

Antal Spector-Zabusky
Antal Spector-Zabusky

Reputation: 36622

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.)

Upvotes: 8

daniel gratzer
daniel gratzer

Reputation: 53871

There are two choices, if your type satisfies the functor laws then the correct trick is

{-# LANGUAGE DeriveFunctor #-}
data SortBinTree a = EmptyNode
                   | Node a (SortBinTree a) (SortBinTree a)
                   deriving Functor
-- Or a manual instance if you have some invariants that
-- need additional jiggering.

And make sure that all it's operations demand an Ord instance. If someone decides to put the tree in a useless state, then it's their own job to fix it.

However for this to work than you must satisfy the functor laws

 fmap id         === id
 fmap f . fmap g === fmap (f . g)

So if you remove duplicates at all from your tree, you're going to be in trouble. This is why Data.Set being an instance of Functor is dubious, it breaks this law.

If you break the laws, then you're simply not a functor. You cannot specify to Haskell that you only want to deal with a subcategory of Hask. In this case you should just define a different function

treeMap :: (Ord a, Ord b) => (a -> b) -> SortBinTree a -> SortBinTree b

In a category theoretic sense, this is still a functor, just not the one that Functor talks about.

Upvotes: 5

Related Questions