Function Equality Notion

Question

Is there any notion of function equality in Scala?

scala> def foo(x: Int) = x + 1
foo: (x: Int)Int

scala> def bar(x: Int) = x + 1
bar: (x: Int)Int

So I can't call == on a function.

scala> foo == bar
<console>:10: error: missing arguments for method foo;
follow this method with `_' if you want to treat it as a partially applied
 function
              foo == bar
              ^

Besides verifying that foo(x) == bar(x) for all x's (not sure how to do that), how else can I verify equality?

Answer 1

TLDR: Yes there is notion of function equality. But it's basic object reference equality, so of very little benefit

• Issue 1: You can call == on function vals - but defs aren't vals.

  You can't call any methods on defs (other than the special case of function application) - because they are not object instances (vals). But you can convert them into vals by calling them (applying), specifying _ for missing params (creating a partially applied function):

  val fooVal = foo(_)  // type is Function1[Int, Int] (from def foo = ...)
  val barVal = bar(_)  // ditto
  
  fooVal == barVal  // == works (returns false)
  foo(_) == bar(_)  // ditto
  

• Issue 2: Function1 has no equals() override defined

  Function1 definition doesn't override equals: https://github.com/scala/scala/tree/v2.10.3/src/library/scala/Function1.scala#L1. Function1 extends AnyRef, thus inheriting functionality of ==/equals/eq:

  • Any.== simply delegates to Any.equals.
  • AnyRef.equals simply delegates to AnyRef.eq, which is a check for equivalence of object references.

  Hence, Function1.== means equivalence of function object (val) references:

  val fooVal = foo(_) 
  val foo2Val = foo(_)
  val foo3Val = fooVal
  val barVal = bar(_) 
  
  fooVal == barVal // returns false
  fooVal == foo2Val // returns false (different objects)
  fooVal == foo3Val // returns true (same object) 
  

• Issue 3: Of course, you can extend Function1 - but how can you define a meaningful equals???

  abstract class MyFunction1[A,B] extends Function1[A,B] {
    // abstract because apply needs to be defined later for each different function
  
    override def equals(other: Any) = 
      // your smart definition here!
  }
  
  val myDoIt1 = new MyFunction1[Int, Int] {
    def apply(x: Int): Int = x + 1
  }
  val myDoIt2 = new MyFunction1[Int, Int] {
    def apply(y: Int): Int = y + 2 -1
  }
  
  // What equals logic could make these two equate? 
  // Would need compilation smarts & logic matching! 
  // Fall-back to class comparison would only work with extensive code design restrictions.
  

Answer 2

Suppose there exists such a function.

/** Decides whether `f1` and `f2` compute the same function. */
def functionEquals[A, B](f1: A => B, f2: A => B): Boolean

Then we could write this:

/** Decides whether `m` halts on input `x`. */
def halts[X](m: X => Unit, x: X): Boolean = 
  !functionEquals[Unit, Unit](
    { _ => while(true)() },
    { _ => m(x) }
  )

Which is, of course, impossible.

Answer 3

Is there any notion of function equality in Scala?

Short and somewhat unhelpful answer is No, you can't write down a general case equality for functions as a consequence of Rice's Theorem. Deducing whether two functions are equal requires proofs about the logic in the function, which can be done in some cases but not in general.

As a silly example consider the fact that we know that any even (expressible as 2*n) number modulus two leaves zero remainder, this is trivial result from elementary school math but it's a piece of knowledge that the compiler would need to have to hypothetically determine whether foo == bar.

def foo(x: Int) = (x*2) % 2
def bar(x: Int) = 0

Scala's type system can encode some of these properties using more complicated types, but not in general.

Answer 4

You wouldn't really expect == to yield anything other than false since == means "has the same memory address" unless it is specifically defined for that class. After all,

scala> class A
scala> (new A) == (new A)
res0: Boolean = false

If Function1 did try to provide an implementation of ==, it's unclear what it would be checking for. Same results under all possible inputs? Same behavior? Same byte code?

If you want a function class that has a well-defined equality operation, you'd have to write it yourself:

class Adder(private val toAdd: Int) extends (Int => Int) {
  override def apply(n: Int) = n + toAdd

  override def equals(other: Any) = other match {
    case o: Adder => this.toAdd == o.toAdd
    case _ => false
  }
}

Then you can do:

scala> val foo = new Adder(1)
foo: Adder = <function1>

scala> val bar = new Adder(1)
bar: Adder = <function1>

scala> foo(2)
res4: Int = 3

scala> foo == bar
res5: Boolean = true

For an even easier solution, just make your class a case class, which gives you equals and hashCode implementations for free:

case class Adder(private val toAdd: Int) extends (Int => Int) {
  override def apply(n: Int) = n + toAdd
}

Answer 5

First off, there is no general equality relation on functions that can be computed (since functions are essentially infinite sets). Depending on the representation of functions, you might be able to get weak equality, though (i.e. both arguments are equal when the result is true but they might also be equal when the result is false).

In scala you might do:

scala> (foo _).equals((bar _ ))
res3: Boolean = false

scala> (foo _) == ((foo _ ))
res5: Boolean = false

The underscore behind the function is a syntactic requirement to distinguish between a zero-argument application and the function value. The equals method (as the ==) is general object equality and thus simply a by-reference comparison. Every evaluation yields a new reference (closure instance). So the equality is weak:

scala> val x = foo _
x: Int => Int = <function1>

scala> x.equals(x)
res7: Boolean = true