Use Unapply to extract identical type classes

Question

I have the following situation, given two types MA and MB, I would like to be able to prove that they both not only have an Applicative but also that they both have the same underlying shape. I tried doing the following:

type UnapplyM[TC[_[_]], MA, M0[_]] = Unapply[TC, MA]{ type M[X] = M0[X] }

implicit def thing[MA, MB, M[_]](implicit un: UnapplyM[Applicative,MA,M], un2: UnapplyM[Applicative,MB,M]) = ...

but keep running into diverging implicits (i.e. this doesn't work.) Similar things can be done with a type projection on the A type param of Unapply and work.

This there a way to take these two types and be able to prove they are, in fact, supported by the same type class instance?

Answer 1

I'll start by saying that a complete answer would be a very long story, and I've told a large part of it in a blog post from last summer, so I'm going to skim over some details here and just provide a working implementation of thing for Cats.

One other introductory note: this machinery now exists in Scalaz, and some of the "review" on my pull request adding it there is one of the many reasons I'm glad Cats exists. :)

First for a totally opaque type class that I won't even try to motivate here:

case class SingletonOf[T, U <: { type A; type M[_] }](
  widen: T { type A = U#A; type M[x] = U#M[x] }
)

object SingletonOf {
  implicit def mkSingletonOf[T <: { type A; type M[_] }](implicit
    t: T
  ): SingletonOf[T, t.type] = SingletonOf(t)
}

Next we can define an IsoFunctor, since Cats doesn't seem to have one at the moment:

import cats.arrow.NaturalTransformation

trait IsoFunctor[F[_], G[_]] {
  def to: NaturalTransformation[F, G]
  def from: NaturalTransformation[G, F]
}

object IsoFunctor {
  implicit def isoNaturalRefl[F[_]]: IsoFunctor[F, F] = new IsoFunctor[F, F] {
    def to: NaturalTransformation[F, F] = NaturalTransformation.id[F]
    def from: NaturalTransformation[F, F] = to
  }
}

We could use something a little simpler than IsoFunctor for what we're about to do, but it's a nice principled type class, and it's what I used in Scalaz, so I'll stick with it here.

Next for an new Unapply that bundles together two Unapply instances:

import cats.Unapply

trait UnapplyProduct[TC[_[_]], MA, MB] {
  type M[X]; type A; type B
  def TC: TC[M]
  type MA_ = MA
  def _1(ma: MA): M[A]
  def _2(mb: MB): M[B]
}

object UnapplyProduct {
  implicit def unapplyProduct[
    TC[_[_]], MA0, MB0,
    U1 <: { type A; type M[_] },
    U2 <: { type A; type M[_] }
  ](implicit
    sU1: SingletonOf[Unapply[TC, MA0], U1],
    sU2: SingletonOf[Unapply[TC, MB0], U2],
    iso: IsoFunctor[U1#M, U2#M]
  ): UnapplyProduct[TC, MA0, MB0] {
    type M[x] = U1#M[x]; type A = U1#A; type B = U2#A
  } = new UnapplyProduct[TC, MA0, MB0] {
    type M[x] = U1#M[x]; type A = U1#A; type B = U2#A
    def TC = sU1.widen.TC
    def _1(ma: MA0): M[A] = sU1.widen.subst(ma)
    def _2(mb: MB0): M[B] = iso.from(sU2.widen.subst(mb))
  }
}

As a historical side note, UnapplyProduct existed for four years in Scalaz before it had any useful instances.

And now we can write something like this:

import cats.Applicative

def thing[MA, MB](ma: MA, mb: MB)(implicit
  un: UnapplyProduct[Applicative, MA, MB]
): Applicative[un.M] = un.TC

And then:

scala> import cats.data.Xor
import cats.data.Xor

scala> thing(Xor.left[String, Int]("foo"), Xor.right[String, Char]('a'))
res0: cats.Applicative[[x]cats.data.Xor[String,x]] = cats.data.XorInstances$$anon$1@70ed21e4

And we've successfully talked the compiler into identifying how to break down these Xor types in such a way that it can see the relevant Applicative instance (which we return).