How does one statisfy a class constraint in an instance of a class that requires a type constructor rather than a concrete type?

Question

I'm currently in Chapter 8 of Learn you a Haskell, and I've reached the section on the Functor typeclass. In said section the author gives examples of how different types could be made instances of the class (e.g Maybe, a custom Tree type, etc.) Seeing this, I decided to (for fun and practice) try implementing an instance for the Data.Set type; in all of this ignoring Data.Set.map, of course.

The actual instance itself is pretty straight-forward, and I wrote it as:

instance Functor Set.Set where
  fmap f empty = Set.empty
  fmap f s = Set.fromList $ map f (Set.elems s)  

But, since I happen to use the function fromList this brings in a class constraint calling for the types used in the Set to be Ord, as is explained by a compiler error:

Error occurred
ERROR line 4 - Cannot justify constraints in instance member binding
*** Expression    : fmap
*** Type          : Functor Set => (a -> b) -> Set a -> Set b
*** Given context : Functor Set
*** Constraints   : Ord b

See: Live Example

I tried putting a constraint on the instance, or adding a type signature to fmap, but neither succeeded (both were compiler errors as well.)

Given a situation like this, how can a constraint be fulfilled and satisfied? Is there any possible way?

Thanks in advance! :)

Answer 1

Unfortunately, there is no easy way to do this with the standard Functor class. This is why Set does not come with a Functor instance by default: you cannot write one.

This is something of a problem, and there have been some suggested solutions (e.g. defining the Functor class in a different way), but I do not know if there is a consensus on how to best handle this.

I believe one approach is to rewrite the Functor class using constraint kinds to reify the additional constraints instances of the new Functor class may have. This would let you specify that Set has to contain types from the Ord class.

Another approach uses only multi-parameter classes. I could only find the article about doing this for the Monad class, but making Set part of Monad faces the same problems as making it part of Functor. It's called Restricted Monads.

The basic gist of using multi-parameter classes here seems to be something like this:

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

instance (Ord a, Ord b) => Functor' Data.Set.Set a b where
  fmap' = Data.Set.map

Essentially, all you're doing here is making the types in the Set also part of the class. This then lets you constrain what these types can be when you write an instance of that class.

This version of Functor needs two extensions: MultiParamTypeClasses and FlexibleInstances. (You need the first extension to be able to define the class and the second extension to be able to define an instance for Set.)

Haskell : An example of a Foldable which is not a Functor (or not Traversable)? has a good discussion about this.

Answer 2

This is impossible. The purpose of the Functor class is that if you have Functor f => f a, you can replace the a with whatever you like. The class is not allowed to constrain you to only return this or that. Since Set requires that its elements satisfy certain constraints (and indeed this isn't an implementation detail but really an essential property of sets), it doesn't satisfy the requirements of Functor.

There are, as mentioned in another answer, ways of developing a class like Functor that does constrain you in that way, but it's really a different class, because it gives the user of the class fewer guarantees (you don't get to use this with whatever type parameter you want), in exchange for becoming applicable to a wider range of types. That is, after all, the classic tradeoff of defining a property of types: the more types you want to satisfy it, the less they must be forced to satisfy.

(Another interesting example of where this shows up is the MonadPlus class. In particular, for every instance MonadPlus TC you can make an instance Monoid (TC a), but you can't always go the other way around. Hence the Monoid (Maybe a) instance is different from the MonadPlus Maybe instance, because the former can restrict the a but the latter can't.)

Answer 3

You can do this using a CoYoneda Functor.

{-# LANGUAGE GADTs #-}

data CYSet a where
    CYSet :: (Ord a) => Set.Set a -> (a -> b) -> CYSet b

liftCYSet :: (Ord a) => Set.Set a -> CYSet a
liftCYSet s = CYSet s id

lowerCYSet :: (Ord a) => CYSet a -> Set.Set a
lowerCYSet (CYSet s f) = Set.fromList $ map f $ Set.elems s

instance Functor CYSet where
  fmap f (CYSet s g) = CYSet s (f . g)

main = putStrLn . show
  $ lowerCYSet
  $ fmap (\x -> x `mod` 3)
  $ fmap abs
  $ fmap (\x -> x - 5)
  $ liftCYSet $ Set.fromList [1..10]
-- prints "fromList [0,1,2]"