我想这个memoize的：
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
但是，当我试图声明一个内部FIB def ，我得到一个编译错误：
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)
}
上述编译失败error: forward reference extends over definition of value fib case n => fib(n-1) + fib(n-2)
为什么声明val fib内的高清失败，但在外面的类/对象范围的作品？
为了澄清，为什么我可能要申报的范围DEF递归memoized功能 - 这里是我的解决方案的子集和问题：
/**
* 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)
}
Answer 1:
我发现了一个更好的方式使用斯卡拉memoize的：
def memoize[I, O](f: I => O): I => O = new mutable.HashMap[I, O]() {
override def apply(key: I) = getOrElseUpdate(key, f(key))
}
现在，你可以写成如下斐波那契：
lazy val fib: Int => BigInt = memoize {
case 0 => 0
case 1 => 1
case n => fib(n-1) + fib(n-2)
}
这里有一个具有多个参数（在选择功能）：
lazy val c: ((Int, Int)) => BigInt = memoize {
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)
}
而这里的子集和问题：
// is there a subset of s which has sum = t
def isSubsetSumAchievable(s: Vector[Int], t: Int) = {
// f is (i, j) => Boolean i.e. can the first i elements of s add up to j
lazy val f: ((Int, Int)) => Boolean = memoize {
case (_, 0) => true // 0 can always be achieved using empty list
case (0, _) => false // we can never achieve non-zero if we have empty list
case (i, j) =>
val k = i - 1 // try the kth element
f(k, j - s(k)) || f(k, j)
}
f(s.length, t)
}
编辑：由于下面讨论的，这里是一个线程安全版本
def memoize[I, O](f: I => O): I => O = new mutable.HashMap[I, O]() {self =>
override def apply(key: I) = self.synchronized(getOrElseUpdate(key, f(key)))
}
Answer 2:
类/性状水平val编译的方法和专用变量的组合。 因此，一个递归定义是允许的。
当地val ，另一方面s为只是普通的变量，因而递归定义是不允许的。
顺便说一句，即使def您定义的工作，它不会做你期望的。 对每次调用foo新函数对象fib将被创建，它将拥有自己的后盾地图。 什么，你应该做的，而不是这个（如果你真的想要一个def成为你的公共接口）：
private val fib: Memo[Int, BigInt] = Memo {
case 0 => 0
case 1 => 1
case n => fib(n-1) + fib(n-2)
}
def foo(n: Int) = {
fib(n)
}
Answer 3:
Scalaz有一个解决方案，为什么不重用呢？
import scalaz.Memo
lazy val fib: Int => BigInt = Memo.mutableHashMapMemo {
case 0 => 0
case 1 => 1
case n => fib(n-2) + fib(n-1)
}
你可以阅读更多有关在Scalaz记忆化 。
Answer 4:
易变的HashMap不是线程安全的。 还限定case语句分别为基础的条件似乎没有必要进行特殊处理，而地图的可装载的初始值并传递给Memoizer。 以下是Memoizer的地方接受备忘录（不可变的映射）和公式，并返回一个递归函数签名。
Memoizer会是什么样子
def memoize[I,O](memo: Map[I, O], formula: (I => O, I) => O): I => O
现在给出以下公式斐波纳契，
def fib(f: Int => Int, n: Int) = f(n-1) + f(n-2)
与Memoizer斐波纳契可以被定义为
val fibonacci = memoize( Map(0 -> 0, 1 -> 1), fib)
其中上下文无关的通用Memoizer被定义为
def memoize[I, O](map: Map[I, O], formula: (I => O, I) => O): I => O = {
var memo = map
def recur(n: I): O = {
if( memo contains n) {
memo(n)
} else {
val result = formula(recur, n)
memo += (n -> result)
result
}
}
recur
}
类似地，对于阶乘，公式是
def fac(f: Int => Int, n: Int): Int = n * f(n-1)
和阶乘与Memoizer是
val factorial = memoize( Map(0 -> 1, 1 -> 1), fac)
启示：记忆化，由Douglas Crockford的Javascript的好的部分第4章
文章来源: Is there a generic way to memoize in Scala?
