Heiko's Blog

About programming and other fun things

We Are Reactive

Implicits Unchained – Type-safe Equality – Part 3

| Comments

In the last post we have developed a type-wise balanced type-safe equality operation:

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!

Before moving on, let’s discuss two minor issues related to the design and the implementation of the current state of the solution.

First, one can easily create new type class instances for Equality that “override” the default which is based on natural equality, i.e. delegates to ==:

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

scala> implicit val weirdIntEquality = new Equality[Int, Int] {
     |   def areEqual(n: Int, m: Int) = n != m
     | }
weirdIntEquality: name.heikoseeberger.demoequality.TypeWiseBalancedEquality.Equality[Int,Int] = $anon$1@6a5f7445

scala> 1 === 1
res0: Boolean = false

Due to the rules of implicit resolution, all locally defined or imported type class instances override the ones defined in the implicit scope (in the companion object of the type class instance). Therefore it’s easy to override the default.

There are many situations where we want this behavior, but I think that in our use case intuition commands that === – which almost looks like == – behaves like ==. Therefore we need a way to prevent others from creating Equality type class instances. This can easily be achieved by sealing Equality:

1
sealed trait Equality[L, R] {  }

The second issue is related to performance. Currently the Equality type class instances are provided by the polymorphic rightSubtypeOfLeftEquality and leftSubtypeOfRightEquality methods, which create new instances every time they get called. Therefore we add the AnyEquality singleton object and simply use it as the return value for rightSubtypeOfLeftEquality and leftSubtypeOfRightEquality:

1
2
3
4
5
6
7
8
9
implicit def rightSubtypeOfLeftEquality[L, R <: L]: Equality[L, R] =
  AnyEquality.asInstanceOf[Equality[L, R]]

implicit def leftSubtypeOfRightEquality[R, L <: R]: Equality[L, R] =
  AnyEquality.asInstanceOf[Equality[L, R]]

private object AnyEquality extends Equality[Any, Any] {
  override def areEqual(left: Any, right: Any): Boolean = left == right
}

The type cast looks ugly, but thanks to type erasure it doesn’t cause any problems.

All right, that’s our final solution for type-wise balanced type-safe equality. Here is the complete code:

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!")
  sealed trait Equality[L, R] {
    def areEqual(left: L, right: R): Boolean
  }
  object Equality extends LowPriorityEqualityImplicits {
    implicit def rightSubtypeOfLeftEquality[L, R <: L]: Equality[L, R] =
      AnyEquality.asInstanceOf[Equality[L, R]]
  }
  trait LowPriorityEqualityImplicits {
    implicit def leftSubtypeOfRightEquality[R, L <: R]: Equality[L, R] =
      AnyEquality.asInstanceOf[Equality[L, R]]
  }
  private object AnyEquality extends Equality[Any, Any] {
    override def areEqual(left: Any, right: Any): Boolean =
      left == right
  }
}

View-wise balanced type-safe equality

While this type-wise balanced type-safe equality operation works in most cases, there are still some glitches:

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

The types in this example – Int and Long – are not in a subtype relationship and therefore our type-wise === doesn’t work. Well, while this is how we designed it, this behavior is kind of odd, because there is a certain relationship between Int and Long: a view-based one. That is, there is an implicit conversion from Int to Long which is the reason why we can assign Int values to Long variables:

1
2
scala> val l: Long = 1
l: Long = 1

While it is not a “must”, it’s reasonable to argue that type-safe equality should also work for types which are in a view-based relationship. So let’s add a view-based === to our solution!

Most of TypeWiseBalancedEquality can be copied over to ViewWiseBalancedEquality. The only difference is the type class instances. These have to be provided the following way:

1
2
3
4
5
6
7
8
9
10
11
12
implicit def rightToLeftEquality[L, R](implicit view: R => L): Equality[L, R] =
  new RightToLeftViewEquality(view)
implicit def leftToRightEquality[L, R](implicit view: L => R): Equality[L, R] =
  new LeftToRightViewEquality(view)
private class LeftToRightViewEquality[L, R](view: L => R) extends Equality[L, R] {
  override def areEqual(left: L, right: R): Boolean =
    view(left) == right
}
private class RightToLeftViewEquality[L, R](view: R => L) extends Equality[L, R] {
  override def areEqual(left: L, right: R): Boolean =
    left == view(right)
}

As you can see, we need to reqire implicit conversions from the left type to the right or vice versa to be in scope for the type class instances. With these changes we make the above example work:

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

scala> 1 === 1L
res0: Boolean = true

scala> 1L === 1
res1: Boolean = true

OK, we’re done, that’s our solution for view-wise balanced type-safe equality. Here is the complete code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
object ViewWiseBalancedEquality {
  implicit class Equal[L](val left: L) extends AnyVal {
    def ===[R](right: R)(implicit equality: Equality[L, R]): Boolean =
      equality.areEqual(left, right)
  }
  @implicitNotFound("ViewWiseBalancedEquality requires ${L} and ${R} to be in an implicit conversion relationship, i.e. one can be viewed as the other!")
  sealed trait Equality[L, R] {
    def areEqual(left: L, right: R): Boolean
  }
  object Equality extends LowPriorityEqualityImplicits {
    implicit def rightToLeftEquality[L, R](implicit view: R => L): Equality[L, R] =
      new RightToLeftViewEquality(view)
  }
  trait LowPriorityEqualityImplicits {
    implicit def leftToRightEquality[L, R](implicit view: L => R): Equality[L, R] =
      new LeftToRightViewEquality(view)
  }
  private class LeftToRightViewEquality[L, R](view: L => R) extends Equality[L, R] {
    override def areEqual(left: L, right: R): Boolean =
      view(left) == right
  }
  private class RightToLeftViewEquality[L, R](view: R => L) extends Equality[L, R] {
    override def areEqual(left: L, right: R): Boolean =
      left == view(right)
  }
}

Conclusion

In this post we have improved the type-wise balanced type-safe equality and also added a view-based one. I think that type-safe equality is very important and therefore wonder whether the sample code which is available on GitHub should be “lifted” to something like a “util-equality” project. What do you think?

Comments