Check value equality between objects with lambdas

Question
1

I need to check if two objects of the same class are “same” in terms of their properties (like case classes). Except their properties include a contextual lambda function, so

  1. I cannot use case classes (contextual lambdas not allowed)
  2. lambdas have unique id’s even if their definition is the same, so comparing the definition doesn’t work.
class O(val f: (x: Int) ?=> Int)
  
O(f = x * 2) == O(f = x * 2)
// false, but I want true

O(f = x * 2) == O(f = x + 1)
// stay false, not same
2

See Comparing two functions without invoking them - #5 by Sporarum

Also note that context function putting the parameter name in scope is probably a bug, and it breaks soundness

1 Like
3

I don’t think so.
IIRC, is just using named tuples.

4

Note that leaving aside the problem of actually comparing contextual lambdas, which seems impossible currently since you can’t talk of their value.

Even if we made them normal lambdas, what you want to do is technically impossible. You would need to solve the halting problem first in order to attempt to check if two different computations are the same or equivalent.
The best you can do is just use reference equality, or maybe some macro to compare their literal bodies (although this still has some limitations).

In general, I would suggest redesign. Have a custom type that wraps over the contextual function, and find a smart way to define equality for that.

1 Like
5

I really doubt so, for example (x: Int, y: Int) ?=> Int doesn’t contain a tuple, (t: (x: Int, y: Int)) ?=> Int does

Also this behaviour precedes named tuples, see this discussion for more details:

1 Like
6

As others have said, this is fundamentally impossible without additional constraints due to the undecidable nature of computation. Because it is undecidable in general, what is likely to happen even if you get kind of close is that you find a hack that kinda works in some cases, and it fails in difficult cases where people are really counting on it to be right.

Therefore, the standard approach if you want to compare computations is to define a canonical form and set of allowed operations and convert them to canonical form. (For instance, if it’s simply predicate logic, you can use deMorgan’s laws etc. to convert to prenex conjunctive normal form, which essentially eliminates arbitrary distinctions between how you write the same logical expression–and this is true even though truth is not computable (c.f. Godel incompleteness).)

Now, it is possible to intercept the expression with a macro and store, say, a hash or some representation of the whole expression tree as part of your object; if you replace class O(val f...) with class O private (val f...) plus object O { apply(f...) it will be syntactically the same. But I very much discourage this. It will be weird and surprising; people will try to do trivial refactorings and everything will break.

So, no, don’t do it this way.

The way you have to do it is to structurally refer to the same computation.

For instance, if you have

val plusOne: Int => Int = _ + 1
val timesTwo: Int => Int => _ * 2

then you can store the function itself, and use reference equality eq to make sure you’re calling the exact same one. If you have a function like

def auto[A](f: A => A)(using A): A = f(summon[A])

you can use it as an adaptor between context functions and regular ones.

But you’re better off not relying on things that make it look like you can write computations in multiple places and they will be correctly unified. This is in general very difficult to make good enough to not be more trouble than it’s worth, and Scala is not one of the languages that places this as a very high priority. Mathematica and other languages with stronger Lisp heritage generally provide more tools that help.

2 Likes