Search code examples
scalascalazscala-2.11scalaz7

Are unboxed tagged types safe?

I've recently heard about unboxed tagged types in scala and while I was trying to learn how exactly it works, I've found this question that points to problems the implementation in scalaz had. One of the consequences of the fix was having to explicit unwrap the tagged type:

def bmi(mass: Double @@ Kg, height: Double @@ M): Double =
  Tag.unwrap(mass) / pow(Tag.unwrap(height), 2)

Then I considered the original idea, where I could do something like:

type Tagged[U] = { type Tag = U }
type @@[T, U] = T with Tagged[U]

trait Kilogram
trait Meter
type Kg = Double @@ Kilogram
type M = Double @@ Meter

def bmi(mass: Kg, height: M): Double = mass / pow(height, 2)

So now I'm wondering whether the issues found previously in scalaz are specific to it's approach, or if the simple implementation could also have problems with erasure, arrays or varargs. The thing is I'm still learning scala, so my understanding of it's type system is quite limited and I couldn't figure it out by myself.

Solution

  • It is unsafe from a type safety perspective. T @@ U is a subtype of T and an instance of T @@ U may be used where ever an instance of T is required, even when it is accidental. Consider the following

    type Tagged[U] = { type Tag = U }
type @@[T, U] = T with Tagged[U]
object Tag {
  def apply[@specialized A, T](a: A): A @@ T = a.asInstanceOf[A @@ T]
}

trait Compare[A] { def compare(a1: A, a2: A): Int }

def useCompare[A: Compare](l: List[A]): Option[A] = 
  l.foldLeft(Option.empty[A])((xs, x) => 
    xs.fold(Some(x))(xxs => 
      if (implicitly[Compare[A]].compare(xxs, x) <= 0) Some(xxs) 
      else Some(x)))

implicit def intCompare: Compare[Int] = new Compare[Int] {
  def compare(a1: Int, a2: Int): Int = 
    a1.compareTo(a2)
}

trait Max
implicit def intCompareMax: Compare[Int @@ Max] = new Compare[Int @@ Max] {
  def compare(a1: Int @@ Max, a2: Int @@ Max): Int = 
    a1.compareTo(a2) * -1
}

scala> val listInts: List[Int] = List(1, 2, 3, 4)
listInts: List[Int] = List(1, 2, 3, 4)

scala> val min = useCompare(listInts)
min: Option[Int] = Some(1)

scala> val listIntMaxs: List[Int @@ Max] = listInts.map(Tag[Int, Max])
listIntMaxs: List[@@[Int,Max]] = List(1, 2, 3, 4)

scala> val max = useCompare(listIntMaxs)
max: Option[@@[Int,Max]] = Some(4)

    OK, everything is cool, right? This is why T @@ U exists. We want to be able to make a new type and define new type classes for it. Unfortunately, everything isn't ok when your coworker comes along and performs some valid refactoring and accidentally breaks your business logic.

    scala> val max = useCompare(listIntMaxs ::: List.empty[Int])
max: Option[Int] = Some(1)

    Oops

    In this case, the use of subtyping, combined with the covariance on the List[+A] type parameter caused a bug. A List[Int @@ Max] may be substituted wherever a List[Int] is needed.