How to add a class constraint to a Functor instance declaration in Haskell?

Question

I have defined the following data type:

data Probability a = PD { mass :: [(a, Ratio Int)] }

Now I want to write that it is an instance of Functor:

collect :: (Eq a, Num b) => [(a, b)] -> [(a, b)]
collect al = map collect' keys where
    keys = nub $ map fst al
    collect' k = (k, sum (map snd (matches k)))
    matches k = filter ((==) k . fst) al

instance (Eq a) => Functor (Probability a) where
    fmap f p = PD (collect $ map (first f) (mass p))

However, I get the following error:

Kind mis-match
The first argument of `Functor' should have kind `* -> *',
but `Probability a' has kind `*'
In the instance declaration for `Functor (Probability a)'

How can I add the necessary Eq a constraint? (I'm using GHC 7.4.1)

You can't add the Eq constraint, because that violates what it means to be an instance of Functor. — Carl
there is a real good talk about this problem here: vimeo.com/69261960 (some of the answers solutions are explained there too) — Random Dev

J. Abrahamson J. Abrahamson · Accepted Answer · 2014-08-17T00:27:22

Sadly, you can't do that—Functor instances must accept any kind of mapping function without restriction.

You can kind of fake it, though.

newtype PF a = PF { unPF :: forall r . Eq r => (a -> r) -> Probability r }

instance Functor PF where
  fmap f (PF p) = PF (\mp -> p (mp . f))

Here, all of the functions that would be mapped over Probability have been "deferred" by PF. We run them all at once by "lowering" back into Probability when possible

lowerPF :: Eq a => PF a -> Probability a
lowerPF pf = unPF pf id

And in order to convert a Probability into a fmappable PF we must "lift" it

liftPF :: Probability a -> PF a
liftPF p = PF $ \mp -> PD (collect $ map (first mp) (mass p))

How to add a class constraint to a Functor instance declaration in Haskell?

2 Answers