How Should We Support "Test" Equal Instances?

[adamgfraser]

We're starting to add instances for more data types that don't have well defined Equal instances. For example, Ord isn't a data type so we can't just look at two Ord values and say whether they are equal. At the same time, we would like to be able to test laws for them to make sure our instances are well behaved.

One approach to do this would be to allow defining some "test" Equal instances. For example, given two Ord[A] values we could say they are equal "as far as we can tell" if they return the same ordering for a random sample of values. We could not know for certain the values are actually equal unless the domain was very small, but this could still probably provide a high degree of confidence in the correctness of instances.

This would probably require performing effects in determining the "to our best knowledge" equality, especially for effect types but would require defining Equal instances that are not "true equality" in some sense, at least within our own internal test suites.

Does this make sense or is there another way we should approach this?

[jdegoes]

There is a more powerful EqualF:

trait EqualSubset[F[_], Subset[_]] {
  def derive[A: Subset](l: F[A], r: F[A]): Equal[F[A]]
}

Such that you can say, EqualSubset[Ord, * => Equal[A] & Enumerable[A]], if you want exhaustivity.

If we want more than that, it won't be generally useful, but it could be useful for testing. Basically we'd need to generate a bunch of input values, feed them into all operations of the type class (e.g. compare), and verify the return values are correct.

[lemastero]

I need a way to compare functions A => B (for https://github.com/zio/zio/issues/4211 and https://github.com/zio/zio-prelude/issues/290). I figured out sth like this:

trait EqualF2[F[-_,+_],B] {
  def deriveEqual[R,A](gen: Gen[R, A], equalB: Equal[B]): RIO[R, Equal[F[A,B]]]
}

object EqualF2 {

  def apply[F[-_,+_],B](implicit equalF: EqualF2[F,B]): EqualF2[F,B] =
    equalF

  implicit def FunctionEqualF[RR,AA,BB](implicit gen: Gen[RR,AA]): EqualF2[Function1,BB] =
    new EqualF2[Function1,BB] {
      override def deriveEqual[R, A](gen: Gen[R, A], equalB: Equal[BB]): RIO[R, Equal[A => BB]] =
        gen.runCollectN(10).flatMap { elems =>
            ZIO.succeed(
              new Equal[A => BB] {
                override def equal(l: A => BB, r: A => BB): Boolean =
                  elems.forall(a => equalB.equal(l(a),r(a)) )
              }
            )
        }
    }
}

so it is "to our best knowledge" approach, where best == 10

[adamgfraser]

@lemastero I think that is fine for testing. I am working on adding an Enumerable type class and then you could say that given an Enumerable[A] and an Equal[B] you could derive an Equal[A => B].