如何实现按名传递参数的结构相等性检查以支持缓存？

核心问题：按名参数的相等性判断 #

按名传递参数（=> A）本质会被包装成无参函数，默认情况下，哪怕两个按名参数对应的计算逻辑完全一致，它们的函数实例也是独立的，直接用==比较会返回false，就像你给出的示例：

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) // 返回 false

原因是comp1和comp2中的f是两个不同的函数实例，默认的引用相等性判断自然不成立。

纯函数场景下的记忆化实现思路 #

既然你假设传入的是纯函数，且目标是扩展scala.util.control.TailCalls实现记忆化，这里提供几种可行方案：

1. 基于输入参数的缓存实现 #

纯函数的输出仅由输入决定，因此可以用输入参数作为缓存的键，存储已计算的TailRec实例。我们可以封装一个工具类来实现：

import scala.util.control.TailCalls._
import scala.collection.mutable

object MemoizedTailCalls {
  private val cache = mutable.Map.empty[Any, TailRec[Any]]

  // 通用记忆化方法：传入唯一标识和待计算的TailRec
  def tailcallMemoized[A](key: Any)(compute: => TailRec[A]): TailRec[A] = {
    cache.getOrElseUpdate(key, compute).asInstanceOf[TailRec[A]]
  }

  // 简化API：针对以Int为参数的函数，自动提取参数作为键
  def tailcallMemoized[A](f: Int => TailRec[A])(n: Int): TailRec[A] = {
    tailcallMemoized(n)(f(n))
  }
}

// 使用示例
import MemoizedTailCalls._

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

// 测试：计算fib(10)会自动缓存中间结果
println(fib(10).result) // 输出55

2. 针对特定函数的局部缓存 #

如果想让API更简洁，可以为每个需要记忆化的函数单独维护缓存，避免全局缓存的耦合：

import scala.util.control.TailCalls._
import scala.collection.mutable

object FibMemo {
  private val cache = mutable.Map.empty[Int, TailRec[Int]]

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

// 调用方式更直观
println(FibMemo.fib(10).result) // 输出55

为什么无法直接比较按名参数的相等性？ #

Scala没有内置机制判断两个按名参数对应的计算逻辑是否等价——函数的逻辑等价性属于不可判定问题（对应停机问题）。在纯函数场景下，我们只能通过输入参数这种外部标识间接实现"逻辑相等"的判断，这也是记忆化的核心思路。

内容的提问来源于stack exchange，提问作者fineThanksAndYou