Two tales of high order functors.

HFunctors.md

There are two possible definitions of a somewhat higher order Functors: HFunctorA:

trait HFunctorA[H[_[_],_]] {
  def map[F[_], G[_], A](h: H[F, A])(f: F ~> G): H[G, A]
}

and HFunctorB:

trait HFunctorB[H[_[_]]] {
  def map[F[_], G[_]](h: H[F])(f: F ~> G): H[G]
}

TLDR; neither are real Functors.

In HFunctorA H[_[_], _] takes in two type parameters, i.e. F[_] and a A. Note that H[_[_], _] doesn't specify the structure between F[_] and A. In cats we have many datatypes that conforms to H[_[_], _], but they don't share the same structure between F[_] and A.
In fact H[_[_], _] can only be deemed it as a Functor from the category of F[_] × A to the category of types (objects being H[F, A] that are concrete types). The category of F[_] × A is the product of the category of endofunctors (objects being F[_]s) and the category of types (objects being As and F[A]s). Since it's a product, we should treat it as a Bifunctor, it's map need to take in two morphisms, one for F[_] and one for A. In another sentence, the map should be really be a bimap that takes two morphisms, one in the category of endofunctors, i.e. a natural transformation, and a morphisms in category of types, i.e. a Function1. I think the following is more appropriate definition:

trait HFunctorA[H[_[_],_]] {
  def bimap[F[_], G[_], A, B](h: H[F, A])(f: F ~> G, g: A => B): H[G, B]
}

Then we can write all the laws etc. But in HFunctorA, we had to fix g to the identity function, so is it really a Functor?

HFunctorB on the other hand, is problematic in it's own way. H[_[_]] can be read as an functor in the category of endofunctors (objects being F[_]s, morphisms being natural transformations). An object in the category of H[_[_]] should be a functor mapped from F[_]. However when you write H[F] in scala, you are fixed to a concrete type, not a Functor (which is represented as a type constructor). So in currrent scala, the fmap of this functor is clearly not really expressible either. So we can't really write this Functor in scala.

I find this definition of HFunctorA misleading:

trait HFunctorA[H[_[_],_]] {
  def map[F[_], G[_], A](h: H[F, A])(f: F ~> G): H[G, A]
}

(because the definition of Functor in Scala is more subtly misleading in the same way). I think it’s clearer to look at it like this:

trait HFunctorA[H[_[_], _]] {
  def hlift[F[_], G[_]](f: F ~> G): H[F, ?] ~> H[G, ?]
}

// which parallels
trait Functor[F[_]] {
  def lift[A, B](f: A => B): F[A] => F[B]
}

This makes it more obvious that HFunctorA is “a functor in the category of endofunctors” (and easily a specialization of some PolyFunctor using kind-polymorphism). I.e., where Functor has the kind * -> *, HFunctorA has the kind (* -> *) -> (* -> *).

However,

trait HFunctorB[H[_[_]]] {
   def hlift[F[_], G[_]](f: F ~> G): H[F] => H[G]
}

doesn’t work the same way.

So Functor is “an endofunctor in Skal”, HFunctorA is “an endofunctor in F[Skal]” (… or something?), and HFunctorB is “a (non-endo) functor from F[Skal] to Skal”.

Thanks very much! @sellout now I can see that HFunctorA is an endofunctor in the category of endofunctors in Skal. The trick is to see H[F, ?] as an endofunctor in Skal as well.