Heiko's Blog

About programming and other fun things

We Are Reactive

Implicits Unchained – Type-safe Equality – Part 2

| Comments

In the last post we have discussed the problems with untyped equality and shown how to provide a simple type-safe equality operation using implicit classes:

1
2
3
4
5
object SimpleEquality {
  implicit class Equal[A](val left: A) extends AnyVal {
    def ===(right: A): Boolean = left == right
  }
}

So why is this solution (too) simple? Let’s look at an example:

1
2
3
4
5
6
7
8
9
10
scala> import name.heikoseeberger.demoequality.SimpleEquality._
import name.heikoseeberger.demoequality.SimpleEquality._

scala> Seq(1, 2, 3) === List(1, 2, 3)
res0: Boolean = true

scala> List(1, 2, 3) === Seq(1, 2, 3)
<console>:11: error: type mismatch;
 found   : Seq[Int]
 required: List[Int]

As you can see, this simple type-safe equality is not type-wise balanced, i.e. it only works if the object on the right is a subtype – including the same type – of the object on the left. The other way round is not possible. Bummer!

The reason is pretty straightforward: When the left object is wrapped into Equal, the type argument A is inferred to the type of this left object. === by its signature requires the right object to be of that type and of course only subtypes, but no supertypes fulfill that constraint.

Type-wise balanced type-safe equality

Like this reason, the solution for this problem is also pretty straightforward: We must additionally allow for the type on the right to be a supertype of the type on the left. In other words, instead of a single constraint RightType subtypeOf LeftType like in the simple approach, we need to enforce either of the two constraints RightType subtypeOf LeftType and LeftType subtypeOf RightType.

Let’s first relax the above constraint by making === itself polymorphic:

1
2
3
4
5
object TypeWiseBalancedEquality {
  implicit class Equal[L](val left: L) extends AnyVal {
    def ===[R](right: R): Boolean = 
  }
}

All right, now we can use supertypes, but also arbitrary types, because we are not enforcing any constraints at all. In order to do so, let’s employ type classes. In Scala a type class is a polymorphic trait and type class instances are implicit values implementing that trait for particular types.

First we define the Equality type class representing equality of two arguments with arbitrary respective types:

1
2
3
4
@implicitNotFound("TypeWiseBalancedEquality requires ${L} and ${R} to be in a subtype relationship!")
trait Equality[L, R] {
  def areEqual(left: L, right: R): Boolean
}

As you can see, we have added a friendly error message if the compiler can’t find a type class instance. Then we add an implicit parameter of type Equality to === and implement === simply by delegating to this parameter:

1
2
3
4
implicit class Equal[L](val left: L) extends AnyVal {
  def ===[R](right: R)(implicit equality: Equality[L, R]): Boolean =
    equality.areEqual(left, right)
}

If we try to call === now, we’ll be out of luck, because the compiler can’t yet find a type class instance:

1
2
3
4
5
scala> import name.heikoseeberger.demoequality.TypeWiseBalancedEquality._
import name.heikoseeberger.demoequality.TypeWiseBalancedEquality._

scala> 1 === 1
<console>:11: error: TypeWiseBalancedEquality requires Int and Int to be in a subtype relationship!

Next we define a type class instance for Equality[L, R] for all L (left type) and R (right type) which fulfill RightType subtypeOf LeftType in the Equality companion object:

1
2
3
4
5
6
object Equality {
  implicit def rightSubtypeOfLeftEquality[L, R <: L]: Equality[L, R] =
    new Equality[L, R] {
      override def areEqual(left: L, right: R): Boolean = left == right
    }
}

Finally we have to define the type class instance for Equality[L, R] for all L (left type) and R (right type) which fulfill LeftType subtypeOf RightType. We can’t define that directly in the Equality companion object, too, because we would run into ambiguity issues if the two types on the left and right are the same. Therefore we move it to a trait we mix into the Equality companion object which results in lower precedence and thus avoids any ambiguities:

1
2
3
4
trait LowPriorityEqualityImplicits {
  implicit def leftSubtypeOfRightEquality[R, L <: R]: Equality[L, R] = 
}
object Equality extends LowPriorityEqualityImplicits {  }

If we look at the above example again, we see that our new type-safe equality operation is balanced:

1
2
3
4
5
6
7
8
9
10
11
scala> import name.heikoseeberger.demoequality.TypeWiseBalancedEquality._
import name.heikoseeberger.demoequality.TypeWiseBalancedEquality._

scala> Seq(1, 2, 3) === List(1, 2, 3)
res0: Boolean = true

scala> List(1, 2, 3) === Seq(1, 2, 3)
res1: Boolean = true

scala> 123 === "a"
<console>:11: error: TypeWiseBalancedEquality requires Int and String to be in a subtype relationship!

Woot!

Here is the current state of our type-wise balanced solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
object TypeWiseBalancedEquality {
  implicit class Equal[L](val left: L) extends AnyVal {
    def ===[R](right: R)(implicit equality: Equality[L, R]): Boolean =
      equality.areEqual(left, right)
  }
  @implicitNotFound("TypeWiseBalancedEquality requires ${L} and ${R} to be in a subtype relationship!")
  trait Equality[L, R] {
    def areEqual(left: L, right: R): Boolean
  }
  object Equality extends LowPriorityEqualityImplicits {
    implicit def rightSubtypeOfLeftEquality[L, R <: L]: Equality[L, R] =
      new Equality[L, R] {
        override def areEqual(left: L, right: R): Boolean = left == right
      }
  }
  trait LowPriorityEqualityImplicits {
    implicit def leftSubtypeOfRightEquality[R, L <: R]: Equality[L, R] =
      new Equality[L, R] {
        override def areEqual(left: L, right: R): Boolean = left == right
      }
  }
}

Conclusion

In this post we have moved from the simple and unbalanced type-safe equality operation from the previous post to a type-wise balanced one. In the next post we’ll look at some minor issues with the current design and implementation of this type-wise balanced solution and also extend it to types which are “compatible” via implicit conversions.

The full source code is available on GitHub.

Comments