我想要进行记忆化处理:
但是当我尝试在
def fib(n: Int) = if(n <= 1) 1 else fib(n-1) + fib(n-2)
println(fib(100)) // times out
我写了以下代码,令人惊讶的是它编译并且可以运行(我感到惊讶是因为fib
在声明中引用了自身):
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))
}
val fib: Memo[Int, BigInt] = Memo {
case 0 => 0
case 1 => 1
case n => fib(n-1) + fib(n-2)
}
println(fib(100)) // prints 100th fibonacci number instantly
但是当我尝试在
def
内部声明fib时,就会出现编译器错误:def foo(n: Int) = {
val fib: Memo[Int, BigInt] = Memo {
case 0 => 0
case 1 => 1
case n => fib(n-1) + fib(n-2)
}
fib(n)
}
以上代码无法编译:错误:前置引用扩展了值fib的定义
case n => fib(n-1) + fib(n-2)
为什么在def内部声明val fib
会失败,但在class/object范围之外声明则可以成功?
为了澄清,为什么我想在def范围内声明递归记忆函数 - 这是我解决子集和问题的方法:
/**
* Subset sum algorithm - can we achieve sum t using elements from s?
*
* @param s set of integers
* @param t target
* @return true iff there exists a subset of s that sums to t
*/
def subsetSum(s: Seq[Int], t: Int): Boolean = {
val max = s.scanLeft(0)((sum, i) => (sum + i) max sum) //max(i) = largest sum achievable from first i elements
val min = s.scanLeft(0)((sum, i) => (sum + i) min sum) //min(i) = smallest sum achievable from first i elements
val dp: Memo[(Int, Int), Boolean] = Memo { // dp(i,x) = can we achieve x using the first i elements?
case (_, 0) => true // 0 can always be achieved using empty set
case (0, _) => false // if empty set, non-zero cannot be achieved
case (i, x) if min(i) <= x && x <= max(i) => dp(i-1, x - s(i-1)) || dp(i-1, x) // try with/without s(i-1)
case _ => false // outside range otherwise
}
dp(s.length, t)
}
lazy val
看起来比每个函数都有2个定义(递归和Y组合)更干净。看看这个链接多么干净。 - pathikrit