Any advantage of using type constructors in type classes?

Question

Take for example the class Functor:

class Functor a
instance Functor Maybe

Here Maybe is a type constructor.

But we can do this in two other ways:

Firstly, using multi-parameter type classes:

class MultiFunctor a e
instance MultiFunctor (Maybe a) a

Secondly using type families:

class MonoFunctor a
instance MonoFunctor (Maybe a)

type family Element
type instance Element (Maybe a) a

Now there's one obvious advantage of the two latter methods, namely that it allows us to do things like this:

instance Text Char

Or:

instance Text
type instance Element Text Char

So we can work with monomorphic containers.

The second advantage is that we can make instances of types that don't have the type parameter as the final parameter. Lets say we make an Either style type but put the types the wrong way around:

data Silly t errorT = Silly t errorT

instance Functor Silly -- oh no we can't do this without a newtype wrapper

Whereas

instance MultiFunctor (Silly t errorT) t

works fine and

instance MonoFunctor (Silly t errorT)
type instance Element (Silly t errorT) t

is also good.

Given these flexibility advantages of only using complete types (not type signatures) in type class definitions, is there any reason to use the original style definition, assuming you're using GHC and don't mind using the extensions? That is, is there anything special you can do putting a type constructor, not just a full type in a type class that you can't do with multi-parameter type classes or type families?

Answer 1

Your proposals ignore some rather important details about the existing Functor definition because you didn't work through the details of writing out what would happen with the class's member function.

class MultiFunctor a e where
    mfmap :: (e -> ??) -> a -> ????

instance MultiFunctor (Maybe a) a where
    mfmap = ???????

An important property of fmap at the moment is that its first argument can change types. fmap show :: (Functor f, Show a) => f a -> f String. You can't just throw that away, or you lose most of the value of fmap. So really, MultiFunctor would need to look more like...

class MultiFunctor s t a b | s -> a, t -> b, s b -> t, t a -> s where
    mfmap :: (a -> b) -> s -> t

instance (a ~ c, b ~ d) => MultiFunctor (Maybe a) (Maybe b) c d where
    mfmap _ Nothing = Nothing
    mfmap f (Just a) = Just (f a)

Note just how incredibly complicated this has become to try to make inference at least close to possible. All the functional dependencies are in place to allow instance selection without annotating types all over the place. (I may have missed a couple possible functional dependencies in there!) The instance itself grew some crazy type equality constraints to allow instance selection to be more reliable. And the worst part is - this still has worse properties for reasoning than fmap does.

Supposing my previous instance didn't exist, I could write an instance like this:

instance MultiFunctor (Maybe Int) (Maybe Int) Int Int where
    mfmap _ Nothing = Nothing
    mfmap f (Just a) = Just (if f a == a then a else f a * 2)

This is broken, of course - but it's broken in a new way that wasn't even possible before. A really important part of the definition of Functor is that the types a and b in fmap don't appear anywhere in the instance definition. Just looking at the class is enough to tell the programmer that the behavior of fmap cannot depend on the types a and b. You get that guarantee for free. You don't need to trust that instances were written correctly.

Because fmap gives you that guarantee for free, you don't even need to check both Functor laws when defining an instance. It's sufficient to check the law fmap id x == x. The second law comes along for free when the first law is proven. But with that broken mfmap I just provided, mfmap id x == x is true, even though the second law is not.

As the implementer of mfmap, you have more work to do to prove your implementation is correct. As a user of it, you have to put more trust in the implementation's correctness, since the type system can't guarantee as much.

If you work out more complete examples for the other systems, you find that they have just as many issues if you want to support the full functionality of fmap. And this is why they aren't really used. They add a lot of complexity for only a small gain in utility.

Answer 2

Well, for one thing the traditional functor class is just much simpler. That alone is a valid reason to prefer it, even though this is Haskell and not Python. And it also represents the mathematical idea better of what a functor is supposed to be: a mapping from objects to objects (f :: *->*), with extra property (->Constraint) that each (forall (a::*) (b::*)) morphism (a->b) is lifted to a morphism on the corresponding object mapped to (-> f a->f b).
None of that can be seen very clearly in the * -> * -> Constraint version of the class, or its TypeFamilies equivalent.

On a more practical account, yes, there are also things you can only do with the (*->*)->Constraint version.

In particular, what this constraint guarantees you right away is that all Haskell types are valid objects you can put into the functor, whereas for MultiFunctor you need to check every possible contained type, one by one. Sometimes that's just not possible (or is it?), like when you're mapping over infinitely many types:

data Tough f a = Doable (f a)
               | Tough (f (Tough f (a, a)))

instance (Applicative f) = Semigroup (Tough f a) where
  Doable x <> Doable y = Tough . Doable $ (,)<$>x<*>y
  Tough xs <> Tough ys = Tough $ xs <> ys
  -- The following actually violates the semigroup associativity law. Hardly matters here I suppose...
  xs <> Doable y = xs <> Tough (Doable $ fmap twice y)
  Doable x <> ys = Tough (Doable $ fmap twice x) <> ys

twice x = (x,x)

Note that this uses the Applicative instance of f not just on the a type, but also on arbitrary tuples thereof. I can't see how you could express that with a MultiParamTypeClasses- or TypeFamilies-based applicative class. (It might be possible if you make Tough a suitable GADT, but without that... probably not.)

BTW, this example is perhaps not as useless as it may look – it basically expresses read-only vectors of length 2ⁿ in a monadic state.

Answer 3

The expanded variant is indeed more flexible. It was used e.g. by Oleg Kiselyov to define restricted monads. Roughly, you can have

 class MN2 m a where
     ret2  :: a -> m a

 class (MN2 m a, MN2 m b) => MN3 m a b where
     bind2 :: m a -> (a -> m b) -> m b

allowing monad instances to be parametrized over a and b. This is useful because you can restrict those types to members of some other class:

import Data.Set as Set

instance MN2 Set.Set a where
    -- does not require Ord
    return = Set.singleton 

instance Prelude.Ord b => MN3 SMPlus a b where
    -- Set.union requires Ord
    m >>= f = Set.fold (Set.union . f) Set.empty m

Note than because of that Ord constraint, we are unable to define Monad Set.Set using unrestricted monads. Indeed, the monad class requires the monad to be usable at all types.

Also see: parameterized (indexed) monad.