Checking structural equality of pass by name parameters

Is there a way to compare if pass by name arguments are equal? Consider the below code

case class Comp[A](f: () => A)
def delay[A](compute: => A) = Comp(() => compute)

def deterministic(x: Int) = x + 1

val comp1 = delay(deterministic(1))
val comp2 = delay(deterministic(1))

println(comp1 == comp2) // Returns false

I know this might not make sense when the passed compute contains side effects, but I want this for caching/memoization purposes and assumption would be passed computation is pure.

I can do that with a wrapper class that takes function and parameters separately, however, it does not look clean for the user of the API that I want to implement.

The thing I would like to do is to extend scala.util.control.TailCalls so that the code would look like

def fib(n: Int): TailRec[Int] =
  if (n < 2) done(n) else for {
    x <- tailcallMemoized(fib(n - 1))
    y <- tailcallMemoized(fib(n - 2))
  } yield x + y

and it gives user the ability to perform computations with memoized results

Solution

By-name params are functions in disguise.

Mathematically 2 functions are equal, if they return the same values for the same inputs. However, you also cannot prove that 2 arbitrary functions (with no extra assumptions) are equal with an algorithm, because halting problem. You can only analyze some special case manually, or limit how you're expressing funtions to some subset of possible representations where such proof would be possible and random by-name param is not constrained in such a way.

However, you can make some assumptions. You can make an assumption that the function is pure - then by-name function, being a function from (): Unit in disguise - accepts only 1 possible value as input, so it can only have possible output.

Then you could call each of these by-name functions, compare the result, and based on that decide if they are equal. However, you'd have to execute each by-name function at least once (then you can cache the output) to know what it returns, so you might want to analyze whether making it by-name offers an actual benefit after all. Perhaps what you want is something like Lazy from Shapeless or Eval from Cats, to make computation lazy but memoized.

Of course, if such code would be used with a side effecting function/by-name, then things might get nasty, so you might want to document it.