Scala Memoization：这个Scala备忘录是如何工作的？

/**
 * Generic way to create memoized functions (even recursive and multiple-arg ones)
 *
 * @param f the function to memoize
 * @tparam I input to f
 * @tparam K the keys we should use in cache instead of I
 * @tparam O output of f
 */
case class Memo[I <% K,O](f: I => O) extends (I => O) {
  import collection.mutable.{Map => Dict}
  type Input = I
  type Key = K
  type Output = O
  val cache = Dict.empty[K,f(x))
}

object Memo {
  /**
   * Type of a simple memoized function e.g. when I = K
   */
  type ==>[I,O] = Memo[I,I,O]
}

在备忘录[I <％K，K，O]中：

I: input
K: key to lookup in cache
O: output

线I<％K表示K可以是从07开始的viewable(即隐式转换)。

在大多数情况下，我应该是K如果你正在写一个类型为Int =>的函数的斐波纳契Int，可以通过Int本身缓存。

但是，有时候在写Memoization时，您不想总是通过输入本身(I)来记忆或缓存，而是输入(K)的函数，例如当您编写具有类型(List)的输入的subsetSum算法时[Int]，Int)，你不想使用List [Int]作为缓存中的键，而是希望使用List [Int] .size作为缓存中键的一部分。

所以，这是一个具体的例子：

/**
 * Subset sum algorithm - can we achieve sum t using elements from s?
 * O(s.map(abs).sum * s.length)
 *
 * @param s set of integers
 * @param t target
 * @return true iff there exists a subset of s that sums to t
 */
 def isSubsetSumAchievable(s: List[Int],t: Int): Boolean = {
    type I = (List[Int],Int)     // input type
    type K = (Int,Int)           // cache key i.e. (list.size,int)
    type O = Boolean              // output type      

    type DP = Memo[I,O]

    // encode the input as a key in the cache i.e. make K implicitly convertible from I
    implicit def encode(input: DP#Input): DP#Key = (input._1.length,input._2)   

    lazy val f: DP = Memo {
      case (Nil,x) => x == 0      // an empty sequence can only achieve a sum of zero
      case (a :: as,x) => f(as,x - a) || f(as,x)      // try with/without a.head
    }

    f(s,t)
 }

你可以把这些都缩小成一行：
类型DP = Memo [(List [Int]，Int)，(Int，Int)，Boolean]

对于常见的情况(当I = K时)，您可以简单地执行以下操作：type ==> [I，O] = Memo [I，I，O]
并使用它像calculate the binomial coeff与递归记忆：

/**
   * http://mathworld.wolfram.com/Combination.html
   * @return memoized function to calculate C(n,r)
   */
  val c: (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)
  }

要了解上述语法如何工作，请refer to this question。

这是一个完整的例子，它通过编码输入(Seq，Seq)到(Seq.length，Seq.length)的参数来计算editDistance：

/**
   * Calculate edit distance between 2 sequences
   * O(s1.length * s2.length)
   *
   * @return Minimum cost to convert s1 into s2 using delete,insert and replace operations
   */
  def editDistance[A](s1: Seq[A],s2: Seq[A]) = {

    type DP = Memo[(Seq[A],Seq[A]),Int]
    implicit def encode(key: DP#Input): DP#Key = (key._1.length,key._2.length)

    lazy val f: DP = Memo {
      case (a,Nil) => a.length
      case (Nil,b) => b.length
      case (a :: as,b :: bs) if a == b => f(as,bs)
      case (a,b) => 1 + (f(a,b.tail) min f(a.tail,b) min f(a.tail,b.tail))
    }

    f(s1,s2)
  }

最后，典型的斐波纳契例子：

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

println(fib(100))