Implicits unchained – type-safe equality – part 2

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:

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:

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:

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:

@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:

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:

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:

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:

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:

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:

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.

Implicits unchained – type-safe equality – part 2

Implicits unchained – type-safe equality – part 1

Beside the fusion of object orientation and functional programming, I think that implicits – implicit classes, conversions, parameters and values – are Scala’s most intrinsic feature. They are a very powerful tool and therefore you should follow the Spider-Man principle: “with great power comes great responsibility”. But hey, they also say “no risk no fun”, so let’s fasten our seatbelts and start a discovery tour of implicitlandia.

Use case: type-safe equality

Our discovery tour will be centered around the use case of type-safe equality. In Java and – because of Java compatibility – also in Scala, equality is untyped:

abstract class Any {
  def equals(other: Any): Boolean = …
  …
}

As you can see, equals takes an argument of type Any. Therefore we can compare apples with pies, a Person with an Option[Person], etc. In most cases, this is not what we want, and this can lead to errors which are very hard to analyze. Instead, we’d like to have a type-safe equality operation like:

123 === 123 // true
"a" === "b" // false
123 === "a" // Should not compile!

First approach

All right, what we need is a === method that can be called on objects of some type and takes another object of that particular type instead of Any. In other words, we need a polymorphic method:

def ===[A](a: A): Boolean = …

But there is no === on Any or any of the other standard classes. And Scala doesn’t support extension methods, right? Well, not directly, but we can use implicits to achieve the same effect.

The basic idea is quite simple: Wrap an object that needs to be extended with one that provides the “extension method” and define an implicit conversion from the type that is to be extended to the wrapper. In our case the type to be extended is any type, so we have to provide a polymorphic conversion. Since Scala 2.10 these two steps can be unified by providing an implicit class:

object SimpleEquality {
  implicit class Equal[A](left: A) {
    def ===(right: A): Boolean = left == right
  }
}

As implicit classes are desugared into the wrapper class and the implicit conversion by the Scala compiler, they can’t be defined at the top-level. Therefore we define the implicit Equal class inside of the SimpleEquality singleton object. By importing SimpleEquality._ we bring the implicit conversion into scope and can make use of our nice type-safe equality operation:

scala> import name.heikoseeberger.demoequality.SimpleEquality._
import name.heikoseeberger.demoequality.SimpleEquality._

scala> 123 === 123
res0: Boolean = true

scala> "a" === "b"
res1: Boolean = false

scala> 123 === "a"
<console>:11: error: type mismatch;
 found   : String("a")
 required: Int

Nice, eh? Well, some of you might be concerned about the potential performance impact of creating wrapper objects at runtime. Fortunately Scala 2.10 offers value classes, which we can use to avoid this creation of the wrappers. All we have to do is extend from AnyVal and make the wrapped value a val. Then the Scala compiler will inline the “extension methods”. Here is the final state of our first and simple approach:

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

Conclusion

In this post we have discussed the problems with untyped equality and shown how to provide a simple type-safe equality operation using implicit classes. In the next post we’ll look at the drawbacks of our simple solution and provide a more sophisticated one which makes use of more implicit goodness.

The full source code is available on GitHub.

Implicits unchained – type-safe equality – part 1