matching.scala

sealed class Match[A, B] { type τs <: HList }

object Match {
  type Aux[A0, B0, τ0 <: HList] = Match[A0, B0] { type τs = τ0 }
  sealed trait τ
  sealed trait τ1[A]

  implicit def matchEq[A0]: Aux[A0, A0, HNil] =
    new Match[A0, A0]{
      type τs = HNil
    }

  implicit def match0[A0]: Aux[τ, A0, A0 :: HNil] =
    new Match[τ, A0] { type τs = A0 :: HNil }

  implicit def matchTC[F[_], TC[_[_]]]: Aux[TC[τ1], TC[F], F[τ] :: HNil] =
    new Match[TC[τ1], TC[F]] { type τs = F[τ] :: HNil }

  implicit def match1[F[_], A, B](implicit m0: Match[A, B]): Aux[F[A], F[B], m0.τs] =
      new Match[F[A], F[B]] { type τs = m0.τs }

  implicit def match2[F[_, _], A0, A1, B0, B1, τs0 <: HList, τs1 <: HList](implicit m0: Aux[A0, B0, τs0], m1: Aux[A1, B1, τs1], p: Prepend[τs0, τs1]): Aux[F[A0, A1], F[B0, B1], p.Out] =
    new Match[F[A0, A1], F[B0, B1]] { type τs = p.Out }

  def apply[A, B](implicit m: Match[A, B]): Aux[A, B, m.τs] = m
}

Demo:

import Match.τ

  Match[Option[τ], Option[Int]]      // compiles
  Match[List[τ], List[Option[Int]]]  // compiles

  type Foo[α] = List[Option[α]]
  Match[Foo[τ], Foo[Int]]   // compiles
  // Match[Foo[τ], List[Option[Int]]]   // should compile ? does not.

  val m1 = Match[List[Option[τ]], List[Option[Int]]] // compiles
  val m2 = Match[List[Option[τ]], List[Option[Int]]] // compiles

  Match[List[Option[τ]], List[Option[List[Int]]]] // compiles
  Match[List[Option[List[τ]]], List[Option[List[Int]]]] // compiles

  Match[Either[τ, Int], Either[String, Int]] // compiles
  Match[Either[String, τ], Either[String, Int]] // compiles
  Match[List[Either[String, τ]], List[Either[String, Int]]] // compiles
  Match[Option[List[Either[String, τ]]], Option[List[Either[String, Int]]]] // compiles

  // Match[Either[Int, τ], Either[String, Int]] // does not compile
  // Match[Option[τ], List[Option[List[Int]]]] // does not compile
  // Match[List[τ], Option[List[Int]]] // does not compile
  // Match[List[List[τ]], List[Option[List[Int]]]] // does not compile
  // Match[List[List[List[τ]]], List[Option[List[Int]]]] // does not compile

I think the problem with Match[Foo[τ], List[Option[Int]]] lies around those lines :

scala> type Foo[x] = List[Option[x]]
defined type alias Foo

scala> sealed trait t
defined trait t

scala> Inner[Foo[t]]
res2: Inner[List[Option[t]]]{type A = t} = Inner$$anon$1@44e14559

scala> Inner[List[Option[t]]]
res3: Inner[List[Option[t]]]{type A = Option[t]} = Inner$$anon$1@2f03f241

Updated the gist with a new version simpler version supporting multiple matches.
Notice how it extract the types of both matched values in an HList.

scala> Match[Either[τ, τ], Either[List[String], Int]]
res1: jto.validation.free.Match[scala.util.Either[jto.validation.free.Match.τ,jto.validation.free.Match.τ],scala.util.Either[List[String],Int]]{type τs = shapeless.::[List[String],shapeless.::[Int,shapeless.HNil]]} = jto.validation.free.Match$$anon$4@59215c5e

Could you generalize this to handle Match[Functor[τ], Functor[List]]?

@vil1 Yes indeed. Scalac does not de-alias before resolving implicits.
It's annoying but I was expecting it. I used this a number of times to workaround the infamous SI-2712...

@milessabin. I knew you would ask ;)
I think so. I need to create an new type wildcard τ1[_] and maybe Match1 but it should work :)
It should also be possible to use Match[τ1[Int], List[Int]]

I don't see how to completely abstract over arity thought.

Matching Functor:

import cats.Functor
import cats.Functor
import Match.τ
import Match.τ1

scala> Match[Functor[τ1], Functor[List]]
res1: jto.validation.free.Match[cats.Functor[jto.validation.free.Match.τ1],cats.Functor[[+A]List[A]]]{type τs = shapeless.::[List[jto.validation.free.Match.τ],shapeless.HNil]} = jto.validation.free.Match$$anon$3@428ef645

I'm not super satisfied by τs being List[τ] :: HNil thought.