LukaJCB/Rank-N-Bifunctors.md

## Rank-N-Bifunctors.md

      
    Raw
  

              Rank-N-Bifunctors.md
            
          
    Uniting the bifunctor and monofunctor hierarchies

With the rise of so-called bifunctor IO types, such as ZIO,
questions have naturally arisen of how one could leverage the cats-effect type classes to make use of this new power.
So far suggestions have mostly focused on duplicating the existing hierarchy into two distinct branches,
one parameterized over F[_] and another parameterized over F[_, _].
To me this is not a great situation, as now library maintainers would have to write code for both of these hierarchies or choose one and leave the other one in the dust.
Instead we should find a way to unite the two shapes under a single hierarchy.
This is a draft on how to enable this unification using polymorphic function types in Dotty.
Let's begin with the standard Monad and Bifunctor classes:
trait Monad[F[_]] {
  def (fa: F[A]) flatMap[A, B](f: A => F[B]): F[B]
  def (a: A) pure[A]: F[A]
  def (fa: F[A]) map[A, B](f: A => B): F[B]
}

trait Bifunctor[F[_, _]] {
  def (fa: F[A, B]) bimap[A, B, C, D](f: A => C)(g: B => D): F[C, D]
}
Now the interesting bit, is when we want to have a Monad for a type of shape F[E, A].
Naively we could duplicate the hierarchy in place and create new typeclasses for Bimonad, Biapplicative, BiflatMap etc., but I'd like to demonstrate a different route.
Basically something like a Bimonad[F[_, _]] is just a forall E. Monad[F[E, ?]] and in Dotty we can actually encode this!
type Bimonad[F[_, _]] = [E] => () => Monad[[A] =>> F[E, A]]
This might look a bit confusing at first, but it will look better future versions of dotty once partially applying types becomes a feature (akin to what kind-projector does with ?/*)
Now we can write functions using abstract bifunctor shapes:
def bar[F[_, _]: Bimonad: Bifunctor](fa: F[Throwable, Int]): F[String, Int] = {
  implicit def F[E]: Monad[[A] =>> F[E, A]] = implicitly[Bimonad[F]][E]()

  fa.flatMap(_.pure).bimap(_.toString)(identity).flatMap(_.pure)
}
As you can see here we change the error type from Throwable to String, but are still able to call flatMap afterwards.
This is not something we can do without polymorphic function types.
Note here, that the implicit def F is needed because of a restriction in Dotty at the moment, hopefully it will be resolved soon!
You can track the progress of that ticket here: lampepfl/dotty-feature-requests#66
So far so good, we can use both operators like flatMap that come from the monofunctor hierarchy as well as operations like bimap from the bifunctor hierarchy.
The interesting bit is what comes next, when we talk about type classes like MonadError and Bracket:
trait MonadError[F[_], E] extends Monad[F] {
  def (e: E) raiseError[A]: F[A]
  def (fa: F[A]) handle[A](f: E => F[A]): F[A] 
}
Here we want the error type E to be the left side of our bifunctor, so a BimonadError would look like this:
type BimonadError[F[_, _]] = [E] => () => MonadError[[A] =>> F[E, A], E]
Now we'd able to write functions like this:
def bar[F[_, _]: BimonadError: Bifunctor](fa: F[Throwable, Int]): F[String, String] = {
  implicit def F[E]: MonadError[[A] =>> F[E, A], E] = implicitly[BimonadError[F]][E]()

  fa.handle(t => 2.pure).bimap(_.toString)(_ * 3).flatMap(n => n.toString.pure)
}
Pretty neat, if you ask me!
It's easy to extend this to Bracket as well as it's already polymorphic in the error type and has the same shape as MonadError.
If we did the same thing for Concurrent and other type classes in cats-effect, we could make everything bifunctor friendly without duplicating the hierarchy at all.
For a baseline I think this is already pretty good.
It might need a few extra type classes such as this one I came up with a year ago:
trait ErrorControl[F[_, _]] extends Bifunctor[F] {
  def (fa: F[A, B]) controlError[A, B, C, D](f: Either[A, B] => F[C, D]): F[C, D]
}
Which would mean we could recover from errors and let that be shown in the type signatures themselves.
Potential usage could look like this:
def baz[F[_, _]: ErrorControl: BimonadError](fa: F[Throwable, Int]): F[String, Int] = {
  implicit def F[E]: MonadError[[A] =>> F[E, A], E] = implicitly[BimonadError[F]][E]()
  fa.controlError { 
    case Left(t) => 3.pure
    case Right(n) => (n + 1).toString.raiseError
  }
}
Anyways that's all for now, I hope we can find a way to make this more ergonomic and usable so that we can enjoy the best of both worlds in the future.
I'm very excited to see what's going to happen and what new and interresting stuff we can come up with.
If you have any comments, concerns or suggestions, please do leave a comment :)