Mario Galic
Mario Galic

Reputation: 48430

Implementing value equality of functions

How to override equals to check value equivalence of functions in specific cases? For example, say we have the following f and g functions

val f = (x: Int) => "worf" + x
val g = (x: Int) => "worf" + x

How could we make assert(f == g) pass?

I tried extending Function1 and implemented equality via generator like so

trait Function1Equals extends (Int => String) {
  override def equals(obj: Any): Boolean = {
    val b = obj.asInstanceOf[Function1Equals]
    (1 to 100).forall { _ =>
      val input = scala.util.Random.nextInt
      apply(input) == b(input)
    }
  }
}

implicit def functionEquality(f: Int => String): Function1Equals = (x: Int) => f(x)

but could not get implicit conversion to work on == perhaps due to this. Scalactics's TripleEquals comes close

import org.scalactic.TripleEquals._
import org.scalactic.Equality

implicit val functionEquality = new Equality[Int => String] {
  override def areEqual(a: Int => String, b: Any): Boolean =
    b match {
      case p: (Int => String) =>

        (1 to 100).forall { _ =>
          val input = scala.util.Random.nextInt
          a(input) == p(input)
        }

      case _ => false
    }
}

val f = (x: Int) => "worf" + x
val g = (x: Int) => "worf" + x
val h = (x: Int) => "picard" + x


assert(f === g) // pass
assert(f === h) // fail

How would you go about implementing equality of functions, preferably using regular ==?

Upvotes: 3

Views: 134

Answers (1)

slouc
slouc

Reputation: 9698

First of all, function equality is not a simple topic (spoiler: it cannot be implemented correctly; see e.g. this question and the corresponding answer), but let's assume that your method of "asserting same output for a hundred random inputs" is good enough.

The problem with overriding == is that it's already implemented for Function1 instances. So you have two options:

  • define a custom trait (your approach) and use ==
  • define a typeclass with operation isEqual and implement it for Function1

Both options have trade-offs.

In the first case, instead of using standard Scala Function1 trait, you have to wrap each function into your custom trait instead. You did that, but then you tried to implement an implicit conversion that will do the conversion from standard Function1 to Function1Equals for you "behind the scenes". But as you realised yourself, that cannot work. Why? Because there already exists a method == for Function1 instances, so there's no reason for the compiler to kick off the implicit conversion. You have to wrap each Function1 instance into your custom wrapper so that the overridden == gets called.

Here's the example code:

trait MyFunction extends Function1[Int, String] {
  override def apply(a: Int): String
  override def equals(obj: Any) = {
    val b = obj.asInstanceOf[MyFunction]
    (1 to 100).forall { _ =>
      val input = scala.util.Random.nextInt
      apply(input) == b(input)
    }
  }
}

val f = new MyFunction {
  override def apply(x: Int) = "worf" + x 
}
val g = new MyFunction {
  override def apply(x: Int) = "worf" + x
}
val h = new MyFunction {
  override def apply(x: Int) = "picard" + x
}

assert(f == g) // pass
assert(f == h) // fail

Your second option is to keep working with standard Function1 instances, but to use a custom method for equality comparison. This can be easily implemented with a typeclass approach:

  • define a generic trait MyEquals[A] which will have the needed method (let's call it isEqual)
  • define an implicit value which implements that trait for Function1[Int, String]
  • define a helper implicit class which will provide the method isEqual for some value of type A as long as there exists an implicit implementation of MyEquals[A] (and we made sure in the previous step that there is one for MyEquals[Function1[Int, String]])

Then the code looks like this:

trait MyEquals[A] {
  def isEqual(a1: A, a2: A): Boolean
}

implicit val function1EqualsIntString = new MyEquals[Int => String] {
  def isEqual(f1: Int => String, f2: Int => String) =
    (1 to 100).forall { _ =>
      val input = scala.util.Random.nextInt
      f1(input) == f2(input)
   }
}

implicit class MyEqualsOps[A: MyEquals](a1: A) {
  def isEqual(a2: A) = implicitly[MyEquals[A]].isEqual(a1, a2)
}

val f = (x: Int) => "worf" + x
val g = (x: Int) => "worf" + x
val h = (x: Int) => "picard" + x

assert(f isEqual g) // pass
assert(f isEqual h) // fail

But as I said, keeping the advantages of first approach (using ==) and second approach (using standard Function1 trait) is not possible. I would argue however that using == isn't even an advantage. Read on to find out why.

This is a good demonstration of why typeclasses are useful and more powerful than inheritance. Instead of inheriting == from some superclass object and overriding it, which is problematic for types we cannot modify (such as Function1), there should instead be a typeclass (let's call it Equal) which provides the equality method for a lot of types.

So if an implicit instance of Equal[Function1] doesn't already exist in the scope, we simply provide our own (like we did in my second snippet) and the compiler will use it. On the other hand, if an implicit instance of Equal[Function1] already does exist somewhere (e.g. in the standard library), it changes nothing for us - we still simply need to provide our own, and it will "override" the existing one.

And now the best part: such typeclass already exists in both scalaz and cats. It is called Equal and Eq respectively, and they both named their equality comparison method ===. This is why I said earlier that I wouldn't even consider being able to use == as an advantage. Who needs == anyway? :) Using scalaz or cats in your codebase consistently would mean that you would rely on === instead of == everywhere, and your life would be simple(r).

But don't count on function equality; that whole requirement is weird and not good. I answered your question pretending that it's fine in order to provide some insights, but the best answer would have been - don't rely on function equality at all.

Upvotes: 5

Related Questions