[Haskell-cafe] Removing polymorphism from type classes (viz. Functor)

[George Pollard]

Ok, so I have a small idea I'm trying to work on; call it a
Prelude-rewrite if you want. For this I want to be able to have the
hierarchy Functor → Applicative → Monad.

For Functor, I would like to be able to implement it for a wider
variety of types, as there are types which have aren't polymorphic
which would also benefit from having an instance.
My running example for this set of types is ByteString; the module
contains the method:

    map ∷ (Word8 → Word8) → ByteString → ByteString

However, we cannot use this for Functor because ByteString isn't
polymorphic. To get around this, I devised the following:

Introduce a type family which represents ‘points’ inside the type:

    type family Point f ∷ ★

For ByteString we have:

    type instance Point ByteString = Word8

For a polymorphic example (lists) we have:

    type instance Point [a] = a

Now Functor becomes:

    class SimpleFunctor f where
        fmap ∷ (Point f → Point f) → (f → f)

However, this doesn't allow for the existence of functions with the
type (a → b). I need to introduce another type into the class:

    class Functor f g where
        fmap ∷ (Point f → Point g) → (f → g)

But having two types isn't very nice (for one thing we can't introduce
a fundep because for lists as it fails one of the coverage
conditions), so introduce another type family to represent types which
can be produced by giving a free variable:

    type Subst f a ∷ ★
    type Subst [a] b = [b]
    type Subst ByteString b = ByteString

    class Functor f where
        fmap ∷ (Point f → Point (Subst f a)) → (f → Subst f a)

I'm not sure how much of a hack this is, or if there is a better way.
It seems to be OK...

Now I want to implement Applicative. It would make sense to have
‘return’ be split out into a separate class, because this can be
restricted in a similar way to Functor:

    class Pointed f where
        return ∷ Point f → f

    instance Pointed [a] where
        return x = [x]

    instance Pointed ByteString where
        return = BS.singleton

Now, I want to be able to restrict Applicative to things which have
[Pointed f, and forall a b. Point f ~ (a → b)]. At the moment I can't
figure this out because I believe it would require something like the
‘quantified contexts’ proposal:

    class (Pointed f, ∀ a b. Point f ~ (a → b)) ⇒ Applicative f where
        ...

I could have something like:

    class (Pointed f, Point f ~ (a → b)) ⇒ Applicative f a b where
        apply ∷ f → Subst f a → Subst f b

This is still not very nice, because it requires two more type
variables in the class, and the non-type-families version is far more
straightforward... in fact, it makes sense for the Applicative class
to have a polymorphic type because it must be able to have ‘return’
applied to arbitrary functions (remember [fmap f xs ≡ return f `apply`
xs]). So back to:

    class Applicative f where
        apply ∷ f (a → b) → f a → f b

But then ‘return’ cannot be added via a superclass restriction to
Pointed! I seem to have painted myself into a corner. Does anyone see
a better way to go about this?

Thanks,
- George