TFunctor for monad transformers

[kailuowang]

As a continuation of #1713 and #1492. I am working on a PR

/**
 * This is an endofunctor in the category of endofunctors in `Skal`.
 *
 * `Skal` is the category of scala types. Functors in `Skal`
 * is encoded as `Functor`. The functors in `Skal` themselves forms
 * a category, let's denote it as `F[Skal]`.
 * In `F[Skal]`, functors of Skal, e.g. `Option[_]` and `Either[E, _]`, are objects,
 * while natural transformations, e.g. `Option ~> Either[E, ?]`, are arrows.
 * A endofunctor in `F[Skal]` maps one set of functors of `Skal` to another
 * set of functors of `Skal` while preserving the structures.
 *
 * For `TFunctor`, the domain is `F[_]`, the codomain is `H[F, _]`, both are
 * functors in `Skal`. The `TFunctor` provides a mapping from the arrows between
 * `F[_]` and `G[_]`, i.e. `F ~> G` to arrows between `H[F, _]` and `H[G, _]`,
 * i.e. `H[F, ?] ~> H[G, ?]`. The `lift` method makes this intention clear.
 *
 * In `cats.core`, examples of such `TFunctor`s are monad transformers such
 * as `OptionT`, `EitherT`
 *
 */
@typeclass trait TFunctor[H[_[_], _]] {
  def map[F[_], G[_], A](h: H[F, A])(f: F ~> G): H[G, A]

  def lift[F[_], G[_]](f: F ~> G): H[F, ?] ~> H[G, ?] =
    λ[H[F, ?] ~> H[G, ?]](hf => map(hf)(f))
}

[cosmin33]

This is the class called Hoist in scalaz (but with Monad requirement on F). There is also Cohoist with ~the same signature (but asking for Comonad in F). I think Hoist is the class corresponding with abstraction underlying mapk functions from all cats transformers (hence the Monad requirement from scalaz typeclass). And there is also the higher level version from Greg Pfeil's work:

trait ExofunctorK[⟹[_[_], _[_]], ⟾[_[_], _[_]], F[_[_], _]] {
    def map[A[_], B[_]](f: A ⟹ B): F[A, ?] ⟾ F[B, ?]
}
type EndofunctorK[⟹[_[_], _[_]], F[_[_], _]]
type Hoist[F[_[_], _]] = ExofunctorK[~>, ~>, F]

Here Hoist is an endofunctor in the nat-trans category

[djspiewak]

Shouldn't this be FunctorK, keeping with the cats naming convention?

[cosmin33]

There is also the cats-tagless direction of higher-kind traits. Both up their kindness towards different shapes. In comparison, along with their semigroupal class (cats-tagless FunctorK versus functork candidate named Hoist):

// here functor maps F ~> G to A[F] => A[G], so it's an exofunctor from ~> to =>
  trait FunctorK[A[_[_]]] { //extends InvariantK[A] {
    def mapK[F[_], G[_]](af: A[F])(fk: F ~> G): A[G]
  }
  trait SemigroupalK[A[_[_]]] {
    def productK[F[_], G[_]](af: A[F], ag: A[G]): A[Tuple2K[F, G, ?]]
  }
// here functor maps F ~> G to A[F, ?] ~> A[G, ?], so it's an endofunctor in ~>
  trait HFunctorK[F[_[_], _]] {
    def mapK[M[_], N[_]](f: M ~> N): F[M, ?] ~> F[N, ?]
  }
  trait HSemigroupalK[T[_[_], _]] {
    def productk2[F[_], G[_]]: λ[t => (T[F, t], T[G, t])] ~> T[Tuple2K[F, G, ?], ?]
  }

FunctorK may be anyone of the above, depending on the frequency of use or maybe finding better anchoring in cat-theory..

[cosmin33]

In my experience, the cats-tagless encoding have proved more useful because the Hoist functor has to be constrained in the M[] parameter to be truly useful. And in this encoding that is a constraint you cannot put, M[] parameter being inside the trait. That is why scalaz chose to constrain it to Monad (and Comonad for the covariant Cohoist) from the start:

trait Hoist[A[_[_], _]] extends MonadTrans[A] {
  def hoist[F[_]: Monad, G[_]](f: F ~> G): A[F, ?] ~> A[G, ?]
}

... downgrading it from a Functor in the ~> category to a functor in a subcategory of "~>" (one that has a Monad/Comonad constraint on the codomain) Instead, cats-tagless style FunctorK+CovariantK like these:

trait FunctorK[A[_[_]]] extends InvariantK[A] {
  def mapK[F[_], G[_]](af: A[F])(fk: F ~> G): A[G]
  override def imapK[F[_], G[_]](af: A[F])(fk: F ~> G)(gK: G ~> F): A[G] = mapK(af)(fk)
}
trait ContravariantSemigroupalK[A[_[_]]] extends SemigroupalK[A] with ContravariantK[A] {
  def contramap2K[F[_], G[_], H[_]](af: A[F], ag: A[G])(f: H ~> Tuple2K[F, G, ?]): A[H] =
    contramapK(productK(af, ag))(f)
}

... and derived traits (Semigroupal.Monoidal | Inv/Con/Cov-ariant combinations, (co)-monadic, ..) gives you the possibility to combine algebras for specific combinations of F and G in which you can freely choose their power in the definition of F ~> G. And also, exemplified above, contravariance traits, just like the covariant ones are both derived from SemigroupalK being duals to each other in beautiful simetry, as in the lower-kinded cats counterparts. As opposed to the scalaz Hoist-Cohoist pair which separate from the start two traits for contravariant and covariant transformers, each limited to a subcategory of the nat-trans (for Hoist: F:Monad ~> G, for Cohoist: F: Comonad ~> G). However, this is just a truly narrow point of view in the vast space of possibilities opened by these encodings, was shy to even mention it.

[LukaJCB]

I think this discussion is super interesting, I wonder if maybe we should move the FunctorK classes to cats-core at some point

[LukaJCB]

Sorry for the accidental close