Kevin Meredith
Kevin Meredith

Reputation: 41939

Function Equality Notion

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?

Upvotes: 1

Views: 242

Answers (5)

Glen Best
Glen Best

Reputation: 23115

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.
    

Upvotes: 1

Chris Martin
Chris Martin

Reputation: 30756

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.

Upvotes: 2

Stephen Diehl
Stephen Diehl

Reputation: 8439

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.

Upvotes: 1

dhg
dhg

Reputation: 52701

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
}

Upvotes: 5

choeger
choeger

Reputation: 3567

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

Upvotes: 1

Related Questions