在 Scala 中使用 Memo.mutableHashMapMemo 进行斐波那契记忆化

Question

我正在尝试在 Scala 中使用记忆功能实现斐波那契函数

这里给出的一个例子使用了一个 case 语句： 在 Scala 中是否有一种通用的记忆方法？

import scalaz.Memo
lazy val fib: Int => BigInt = Memo.mutableHashMapMemo {
  case 0 => 0
  case 1 => 1
  case n => fib(n-2) + fib(n-1)
}

似乎该变量n被隐式定义为第一个参数，但是如果我替换n为_

此外，lazy关键字在这里有什么优势，因为该函数在使用和不使用此关键字的情况下似乎同样有效。

但是，我想将其概括为具有适当类型的更通用的函数定义

import scalaz.Memo
def fibonachi(n: Int) : Int = Memo.mutableHashMapMemo[Int, Int] {
    var value : Int = 0
    if( n <= 1 ) { value = n; }
    else         { value = fibonachi(n-1) + fibonachi(n-2) }
    return value
}

但我收到以下编译错误

cmd10.sc:4: type mismatch;
 found   : Int => Int
 required: Int
def fibonachi(n: Int) : Int = Memo.mutableHashMapMemo[Int, Int] {
                                                                         ^Compilation Failed
Compilation Failed

所以我试图了解向 scaladef函数添加记忆注释的通用方法

Answer 1

实现斐波那契数列的一种方法是通过递归Stream.

val fib: Stream[BigInt] = 0 #:: fib.scan(1:BigInt)(_+_)

流的一个有趣的方面是，如果有什么东西占据了流的头部，计算结果会被自动记忆。所以，在这种情况下，因为标识符fib是 aval而不是 a def， 的值fib(n)只计算一次，然后简单地检索。

然而，索引 aStream仍然是一个线性操作。如果你想记住它，你可以创建一个简单的备忘录包装器。

def memo[A,R](f: A=>R): A=>R =
  new collection.mutable.WeakHashMap[A,R] {
    override def apply(a: A) = getOrElseUpdate(a,f(a))
  }

val fib: Stream[BigInt] = 0 #:: fib.scan(1:BigInt)(_+_)
val mfib = memo(fib)
mfib(99)  //res0: BigInt = 218922995834555169026