Equality of functions in Scala, is functions objects in Scala?

Question

I am reading the book Programming in Scala. In the book, it says that "A function literal is compiled into a class that when instantiated at runtime is a function value". And it mentions that "Function values are objects, so you can store them in variables if you like".

So I try to check the equality between functions. But I failed.

1. If function is object in Scala, then it should behave like other objects in Scala. Maybe check equality of function is meaningless, so it is disabled?

2. And will function be compiled into object in Scala?

Answer 1

Lambda are compiled as anonymous classes (not case class, as far as I remember). That means if you do:

val f1: (String) => String = _ => "F1"
val f2: (String) => String = _ => "F2"

Both f1 and f2 are subtype of Function1[String,String], but they are of different anonymous classes, so can't equal.

If you write it as:

case class F(res: String) extends ((String) => String) {
  def apply(s: String) = res
}

Then:

val f1: (String) => String = F("A")
val f2: (String) => String = F("A")
f1 == f2 // true

Answer 2

It's not clear what "equality" of functions means. Typically, what people care about is "do these two functions compute the same result?"

This, however, is a well-known undecidable problem, the Function Problem. The actual proof is more complex, obviously, but a simple intuition is: if you could tell whether two functions were equal, then you could solve the Halting Problem by asking "is this function equal to while (true) {}?"

So, we cannot decide whether two functions compute the same result. What we could do, is for example, check whether they contain the exact same code. But that is pretty boring. Just some tiny compiler optimization or renaming a single variable will make two functions that intuitively should be equal not equal.

Ergo, we take the easy way out: two functions are equal if they are identical, otherwise they aren't.