在Scala中，case class上的"extends (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))
}

对我来说令人困惑的是，case类正在扩展extends (A => B)部分。首先，发生了什么？其次，为什么需要这样做？最后，你称这种继承方式为什么名称或术语？

接下来，我看到Memo在此处被用于计算Fibanocci数。

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

可能是我没有看到所有被应用的“简化”。但是，我无法弄清楚 val 行的结尾，= Memo {。所以，如果这个代码被更冗长地打出来，也许我就能理解关于如何构建Memo的“飞跃”。

非常感谢您提供的任何帮助。谢谢。

- chaotic3quilibrium

---

更多澄清在这里发布：https://dev59.com/U18f5IYBdhLWcg3wB-sU#25129872 - pathikrit

Answer 1

A => B 的缩写是 Function1[A, B]，因此您的 Memo 是从 A 到 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] ...

- 0__

---

太棒了！所以，我认为你的意思是Scala编译器将“extends (A => B)”转换为“extends Function[A, B]”。而Function[A, B]是Scala默认库中已经定义的一个类（或特质？）。Function[A, B]有一个定义好的函数“def apply(x: A): B”，它是抽象的；即没有提供必须被覆盖的实现。这一切都正确吗？那么，这种“extends”的类有一个名称吗？然后，在使用Memo的第二段代码中更明确地发生了什么？ - chaotic3quilibrium

是的，这只是一种替代语法。 - 0__

我已经创建了一个答案，其中包含了您提供的信息。如果您有机会，请检查一下，以确保我捕捉到您提供的所有内容，以防我可能错过了某些超出我能力范围的细微差别。谢谢。 - chaotic3quilibrium

Answer 2

为了补充0_的回答，fibonacci是通过Memo的伴生对象的apply方法实例化的，由于Memo是一个case类，因此编译器会自动生成它的伴生对象。

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

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的一个示例。

如果你跟随那个链接，你会看到PartialFunction扩展了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
})

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

- Nicolas Rinaudo

---

我在你的最后一句话之前都理解得很好，即“传递给apply的模式匹配是PartialFunction1，它是Function1的一个实例。”但是，在那里，我就不明白了。似乎对于“= Memo {...}”部分做出了太多的假设；也就是说，在我无法进行“假设跳跃”的地方，有太多的Scala语法简化。 - chaotic3quilibrium

@chaotic3quilibrium 现在我有一个合适的电脑，我已经添加了正确的代码示例来解释。我希望这能为您澄清问题，尽管 _0 的答案确实是您正在寻找的答案。 - Nicolas Rinaudo

很好，解释得很透彻。这个问题确实有两个部分，所以你和0__都应该得到认可。 - ach

@NicolasRinaudo 如果你有时间的话，能否验证一下我的答案是否正确地融入了你的观点？在Eclipse的ScalaIDE的工作表中它是可行的。我只是想确保我没有错过什么超出我理解范围的微妙之处。 - chaotic3quilibrium

你对PartialFunction的假设是错误的，实际上并没有创建PartialFunction。事实上，只有在编译器明确告知时才会创建它们，例如使用case class Memo[A,B](f: PartialFunction[A,B])。 - kiritsuku

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) 

- pathikrit

---

非常感谢您发布这篇文章。我很喜欢您所做的事情，但是我无法理解您如何充分利用Scala，哈哈！因此，我有一个问题。 :) - chaotic3quilibrium

我之后创建了一个独立的Memo.scala：https://github.com/pathikrit/scalgos/blob/master/src/main/scala/com/github/pathikrit/scalgos/Memo.scala简单使用： https://github.com/pathikrit/scalgos/blob/master/src/main/scala/com/github/pathikrit/scalgos/Combinatorics.scala#L84-L91复杂使用： https://github.com/pathikrit/scalgos/blob/master/src/main/scala/com/github/pathikrit/scalgos/DynamicProgramming.scala#L14-L33 - pathikrit

Answer 4

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

概述：

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

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

详细信息：

定义Memo case类的第一个代码块可以更详细地编写如下：

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
}

第二个定义变量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
    }
  )
}

为了解决第二个代码块中的自引用问题，在case n => fibonacci(n-1) + fibonacci(n-2)这一行中，需要将val添加lazy。

最后，fibonacci的使用示例如下：

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

- chaotic3quilibrium

---

我认为你的第二点是不必要的（也不是真正正确的），因为“override”是一种注释，你添加它只是为了帮助编译器，但它既不是必需的，也不会出现在编译器的输出中。你的第三点有些错误：没有暗示匹配 - a match {... 只是意味着部分函数使用参数a调用，在我们的情况下，它作为参数传递，而不是被调用。第四点是一个简化：部分函数被传递给伴生对象的“apply”方法，然后再传递给构造函数。你关于“lazy”的观点是100%正确的，对此我表示歉意。 - Nicolas Rinaudo

@NicolasRinaudo 我的目的是通过过度冗长来展示所有的假设；即尽可能少地使用编译器简化。因此，在第2项中使用了“override”。顺便说一句，我认为只有在覆盖抽象方法时，“override”才是可选的。当覆盖非抽象方法时，它是必需的，对吧？ - chaotic3quilibrium

关于override: 你是对的，有些情况下需要用到它，但在这种情况下不需要。我认为称编译器假定它存在是不正确的，这只是一种观点问题。至于match，我的理解是a match {…}会生成一个函数并立即将其应用于a - 这与你的情况不同，虽然也会生成一个函数，但不会被应用。你可以随意以自己感到舒适的方式来解释它，我只是认为它不是实际发生的事情的准确描述。虽然我也可能错了。 - Nicolas Rinaudo

@NicolasRinaudo 啊！我明白你在区分什么。它不是一个立即执行的函数。但是，这不是为什么它在PartialFunction内部吗？也就是说，虽然它似乎在apply()中立即评估，但apply()本身直到以后才会执行；即当使用PartialFunction实例时，从而提供了我认为你正在描述的延迟执行。我有什么遗漏吗？如果有的话，您能否建议我如何重写它，使其既是显式匹配又是延迟执行的？ - chaotic3quilibrium

#2 应该是：因为它扩展了 Function1[A, B]，所以必须提供一个具体的 def apply(a: A): B。 - sourcedelica

Answer 5

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

如果没有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方法，从而可以完成一些任务。

- lcn