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
– Carl, Commented Aug 17, 2014 at 0:06
there is a real good talk about this problem here: vimeo.com/69261960 (some of the answers solutions are explained there too) — Random Dev
– Random Dev, Commented Aug 17, 2014 at 6:33

J. Abrahamson · Accepted Answer · 2014-08-17 13:55:21Z

10

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

edited Aug 17, 2014 at 13:55

answered Aug 17, 2014 at 0:27

J. Abrahamson

74.9k9 gold badges142 silver badges184 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

rampion Over a year ago

what is f in liftPF?

J. Abrahamson Over a year ago

Oops, teach me to copy and paste—it was supposed to be mp. I'll fix that.

duplode · Accepted Answer · 2019-06-02 14:02:53Z

7

What you're writing is not a Functor. A Functor's fmap must support arbitrary value types being mapped, not just those that satisfy a certain constraint. You can make it an instance of a more general concept though. For example, the package constrained-categories defines a class of constrained functors.

edited Jun 2, 2019 at 14:02

duplode

34.5k7 gold badges88 silver badges160 bronze badges

answered Aug 17, 2014 at 4:55

Dominique Devriese

3,0931 gold badge17 silver badges21 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related