在Scala中,案例类的"扩展(A => B)"是什么意思？

Question

在研究如何在Scala中进行Memoization时,我发现了一些我没有理解的代码.我试图看看这个特别的"东西",但不知道该怎么称呼它; 即引用它的术语.另外,用符号搜索并不容易,唉!

我在这里看到以下代码在Scala中进行memoization :

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).首先,发生了什么？其次,为什么甚至需要呢？最后,你称之为这种继承; 即是否有一些特定的名称或术语可供我参考？

接下来,我看到这样计算Fibanocci号码使用备注这里:

  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延伸从函数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] ...

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的实例.

如果你按照那个链接,你会看到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会偏离主题和混乱.

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 项中的started 之间的内容{}作为参数传递给 Memo 案例类构造函数
5. {}Scala 假定第 3 项中的 Started之间存在隐含类型PartialFunction[Int, BigInt]，编译器使用“匹配”代码块作为 PartialFunction 方法的重写apply()，然后为 PartialFunction 的 method 提供额外的重写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)