scala - 在 Scala 中，案例类上的“扩展 (A => B)”是什么意思？

Question

在研究如何在 Scala 中进行记忆化时，我发现了一些我不熟悉的代码。我试图查找这个特殊的“东西”，但不知道该怎么称呼它；即指代它的术语。此外，使用符号搜索并不容易，呃！

我在这里看到了以下在 Scala 中进行记忆的代码：

case class Memo[A,B](f: A => B) extends (A => B) {
  private val cache = mutable.Map.empty[A, B]
  def apply(x: A) = cache getOrElseUpdate (x, f(x))
}

这就是案例类正在扩展的内容，这让我感到困惑，这extends (A => B)部分。首先，发生了什么？其次，为什么需要它？最后，你把这种继承叫做什么？即是否有一些特定的名称或术语可以用来指代它？

接下来，我在这里看到以这种方式使用的备忘录来计算斐班诺数：

  val fibonacci: Memo[Int, BigInt] = Memo {
    case 0 => 0
    case 1 => 1
    case n => fibonacci(n-1) + fibonacci(n-2)
  }

我可能没有看到所有正在应用的“简化”。但是，我无法弄清楚该val行的结尾，= Memo {. 因此，如果将其输入得更冗长，也许我会理解有关如何构建备忘录的“飞跃”。

非常感谢您对此的任何帮助。谢谢你。

Answer 1

A => B是 的缩写Function1[A, B]，因此您Memo扩展了一个函数 from Ato B，最显着的定义是通过apply(x: A): B必须定义的方法。

由于“中缀”表示法，您需要在类型周围加上括号，即(A => B). 你也可以写

case class Memo[A, B](f: A => B) extends Function1[A, B] ...

或者

case class Memo[A, B](f: Function1[A, B]) extends Function1[A, B] ...

Answer 2

为了完成 0_ 的答案，fibonacci正在通过Memo伴随对象的 apply 方法实例化，由编译器自动生成，因为Memo它是一个案例类。

这意味着将为您生成以下代码：

object Memo {
  def apply[A, B](f: A => B): Memo[A, B] = new Memo(f)
}

Scala 对该方法有特殊处理apply：调用它时不需要输入它的名称。以下两个调用是严格等价的：

Memo((a: Int) => a * 2)

Memo.apply((a: Int) => a * 2)

该case块称为模式匹配。在底层，它会生成一个偏函数——也就是说，一个为其某些输入参数定义的函数，但不一定是所有输入参数。我不会详细介绍部分函数，​​因为它离题了（这是我写给自己的关于该主题的备忘录，如果你热衷的话），但它在这里的本质意思是该case块实际上是一个PartialFunction的实例。

如果您点击该链接，您会看到PartialFunctionextends Function1 - 这是Memo.apply.

因此，一旦脱糖（如果这是一个词），那段代码的实际含义是：

lazy val fibonacci: Memo[Int, BigInt] = Memo.apply(new PartialFunction[Int, BigInt] {
  override def apply(v: Int): Int =
    if(v == 0)      0
    else if(v == 1) 1
    else            fibonacci(v - 1) + fibonacci(v - 2)

  override isDefinedAt(v: Int) = true
})

请注意，我已经大大简化了模式匹配的处理方式，但我认为开始讨论unapplyandunapplySeq会偏离主题并且令人困惑。

Answer 3

我是这种方式做备忘录的原作者。您可以在同一个文件中看到一些示例用法。由于 Scala 展开元组的方式，当您也想记住多个参数时，它也非常有效：

    /**
     * @return memoized function to calculate C(n,r) 
     * see http://mathworld.wolfram.com/BinomialCoefficient.html
     */
     val c: Memo[(Int, Int), BigInt] = Memo {
        case (_, 0) => 1
        case (n, r) if r > n/2 => c(n, n-r)
        case (n, r) => c(n-1, r-1) + c(n-1, r)
     }
     // note how I can invoke a memoized function on multiple args too
     val x = c(10, 3) 

Answer 4

这个答案是 0__ 和 Nicolas Rinaudo 提供的部分答案的综合。

概括：

Scala 编译器做出了许多方便的（但也高度交织在一起的）假设。

1. Scala 将extends (A => B)其视为extends Function1[A, B]( ScalaDoc for Function1[+T1, -R] )的同义词
2. apply(x: A): B必须提供Function1 继承的抽象方法的具体实现；def apply(x: A): B = cache.getOrElseUpdate(x, f(x))
3. Scala 假设代码块的隐含match以= Memo {
4. Scala将第{}3项开始之间的内容作为参数传递给Memo案例类构造函数
5. Scala 假定{}在第 3 项中开始的隐含类型 asPartialFunction[Int, BigInt]和编译器使用“匹配”代码块作为 PartialFunction 方法的覆盖apply()，然后为 PartialFunction 方法提供额外的覆盖isDefinedAt()。

细节：

定义案例类 Memo 的第一个代码块可以写得更详细：

case class Memo[A,B](f: A => B) extends Function1[A, B] {    //replaced (A => B) with what it's translated to mean by the Scala compiler
  private val cache = mutable.Map.empty[A, B]
  def apply(x: A): B = cache.getOrElseUpdate(x, f(x))  //concrete implementation of unimplemented method defined in parent class, Function1
}

定义 val fibanocci 的第二个代码块可以写得更冗长，如下所示：

lazy val fibonacci: Memo[Int, BigInt] = {
  Memo.apply(
    new PartialFunction[Int, BigInt] {
      override def apply(x: Int): BigInt = {
        x match {
          case 0 => 0
          case 1 => 1
          case n => fibonacci(n-1) + fibonacci(n-2)
        }
      }
      override def isDefinedAt(x: Int): Boolean = true
    }
  )
}

必须添加lazy到第二个代码块的 val 以处理行中的自引用问题case n => fibonacci(n-1) + fibonacci(n-2)。

最后，斐波那契的一个示例用法是：

val x:BigInt = fibonacci(20) //returns 6765 (almost instantly)

Answer 5

关于这一点再多说一句extends (A => B)：extends这里不是必需的，但如果Memo要在高阶函数或类似情况中使用的实例是必需的。

没有 this extends (A => B)，如果您仅在方法调用中使用Memo实例就完全可以了。fibonacci

case class Memo[A,B](f: A => B) {
    private val cache = scala.collection.mutable.Map.empty[A, B]
    def apply(x: A):B = cache getOrElseUpdate (x, f(x))
}
val fibonacci: Memo[Int, BigInt] = Memo {
    case 0 => 0
    case 1 => 1
    case n => fibonacci(n-1) + fibonacci(n-2)
}

例如：

Scala> fibonacci(30)
res1: BigInt = 832040

但是当你想在高阶函数中使用它时，你会遇到类型不匹配错误。

Scala> Range(1, 10).map(fibonacci)
<console>:11: error: type mismatch;
 found   : Memo[Int,BigInt]
 required: Int => ?
              Range(1, 10).map(fibonacci)
                               ^

所以extends这里只有助于将实例标识fibonacci给其他人，它有一个apply方法，因此可以做一些工作。