Quick little demo of type tagging in Scala that doesn't seem to have appreciable overhead for non-primtive types. For primtive types (e.g. `Int`) the overhead is equivalent to the kind of boxing you get with `.sum`.

Tag.scala

package cats

import cats.macros.Tags

object Tag {

  type @@[A, T] = Tags.Tagged[A, T]

  implicit class TagOps[A](a: A) {
    def tag[T]: A @@ T = macro Tags.tagMacro[A, T]
  }

  implicit class UntagOps[A, T](at: A @@ T) {
    def untag: A = macro Tags.untagMacro[A, T]
  }

  implicit class TagfOps[F[_], A](val fa: F[A]) extends AnyVal {
    def tagf[T]: F[A @@ T] = wrapf[F, A, T](fa)
  }

  implicit class UntagfOps[F[_], A, T](val fat: F[A @@ T]) {
    def untagf: F[A] = unwrapf[F, A, T](fat)
  }

  // implicit class TagkOps[F[_[_]], G[_]](val fg: F[G]) extends AnyVal {
  //   def tagk[T]: F[λ[α => G[α] @@ T]] = wrapk[F, G, T](fg)
  // }
  // 
  // implicit class UntagkOps[F[_[_]], G[_], T](val fgt: F[λ[α => G[α] @@ T]]) extends AnyVal {
  //   def untagk: F[G] = unwrapk[F, G, T](fgt)
  // }

  def wrap[A, T](a: A): A @@ T = macro Tags.wrapMacro[A, T]
  def unwrap[A, T](at: A @@ T): A = macro Tags.unwrapMacro[A, T]

  def wrapf[F[_], A, T](fa: F[A]): F[A @@ T] = macro Tags.wrapfMacro[F, A, T]
  def unwrapf[F[_], A, T](fat: F[A @@ T]): F[A] = macro Tags.unwrapfMacro[F, A, T]

  // def wrapk[F[_[_]], G[_], T](fg: F[G]): F[λ[α => G[α] @@ T]] = macro Tags.wrapkMacro[F, G, T]
  // def unwrapk[F[_[_]], G[_], T](fgt: F[λ[α => G[α] @@ T]]): F[G] = macro Tags.unwrapkMacro[F, G, T]

}

Tags.scala

package cats
package macros

import scala.reflect.macros.whitebox.Context

object Tags {

  type Tagged[A, T] = { type Data = A; type Tag = T }

  def tagMacro[A: c.WeakTypeTag, T: c.WeakTypeTag](c: Context): c.Expr[Tagged[A, T]] = {
    import c.universe._
    val AT = weakTypeOf[Tagged[A, T]]
    val a = c.prefix.tree match {
      case Apply(_, List(x)) => x
      case t => c.abort(c.enclosingPosition, s"Cannot extract .tag target (tree = $t)")
    }
    c.Expr[Tagged[A, T]](q"$a.asInstanceOf[$AT]")
  }

  def untagMacro[A: c.WeakTypeTag, T: c.WeakTypeTag](c: Context): c.Expr[A] = {
    import c.universe._
    val A = weakTypeOf[A]
    val at = c.prefix.tree match {
      case Apply(_, List(x)) => x
      case t => c.abort(c.enclosingPosition, s"Cannot extract .untag target (tree = $t)")
    }
    c.Expr[A](q"$at.asInstanceOf[$A]")
  }

  def wrapMacro[A: c.WeakTypeTag, T: c.WeakTypeTag](c: Context)(a: c.Expr[A]): c.Expr[Tagged[A, T]] = {
    import c.universe._
    val A = weakTypeOf[A]
    val T = weakTypeOf[T]
    val AT = weakTypeOf[Tagged[A, T]]
    c.Expr[Tagged[A, T]](q"$a.asInstanceOf[cats.macros.Tags.Tagged[$A, $T]]")
  }

  def unwrapMacro[A: c.WeakTypeTag, T](c: Context)(at: c.Expr[Tagged[A, T]]): c.Expr[A] = {
    import c.universe._
    val A = weakTypeOf[A]
    c.Expr[A](q"$at.asInstanceOf[$A]")
  }

  def wrapfMacro[F[_], A: c.WeakTypeTag, T: c.WeakTypeTag](c: Context)(fa: c.Expr[F[A]])(implicit F: c.WeakTypeTag[F[_]]): c.Expr[F[Tagged[A, T]]] = {
    import c.universe._
    val AT = appliedType(typeOf[Tagged[_, _]], List(weakTypeOf[A], weakTypeOf[T]))
    val FAT = appliedType(F.tpe.typeConstructor, List(AT))
    val t = q"$fa.asInstanceOf[$FAT]"
    c.Expr[F[Tagged[A, T]]](t)
  }

  def unwrapfMacro[F[_], A: c.WeakTypeTag, T](c: Context)(fat: c.Expr[F[Tagged[A, T]]])(implicit F: c.WeakTypeTag[F[_]]): c.Expr[F[A]] = {
    import c.universe._
    val FA = appliedType(F.tpe.typeConstructor, List(weakTypeOf[A]))
    c.Expr[F[A]](q"$fat.asInstanceOf[$FA]")
  }

  // def wrapkMacro[F[_[_]], G[_], T: c.WeakTypeTag](c: Context)(fg: c.Tree)(implicit F: c.WeakTypeTag[F[List]], G: c.WeakTypeTag[G[_]]): c.Tree = {
  //   import c.universe._
  //   val A = internal.typeDef(G.tpe.typeParams.head)
  //   val LGT = typeLambda(c)(List(A), TypeTree(appliedType(G.tpe.typeConstructor, List(A.tpe))))
  //   val FGT = appliedType(F.tpe.typeConstructor, List(LGT))
  //   q"$fg.asInstanceOf[$FGT]"
  // }
  // 
  // def unwrapkMacro[F[_[_]], G[_], T](c: Context)(fgt: c.Tree)(implicit F: c.WeakTypeTag[F[List]], G: c.WeakTypeTag[G[_]]): c.Tree = {
  //   import c.universe._
  //   val FG = appliedType(F.tpe.typeConstructor, List(G.tpe))
  //   q"$fgt.asInstanceOf[$FG]"
  // }
  // 
  // def typeLambda(c: Context)(params: List[c.universe.TypeDef], body: c.universe.TypeTree): c.universe.Type = {
  //   import c.universe._
  //   val L = TypeName("L$")
  //   SelectFromTypeTree(
  //     CompoundTypeTree(
  //       Template(
  //         q"_root_.scala.AnyRef" :: Nil,
  //         ValDef(NoMods, termNames.WILDCARD, TypeTree(), EmptyTree),
  //         TypeDef(NoMods, L, params, body) :: Nil)), L).tpe
  // }
}