我最近在阅读《程序员的范畴论》，其中Bartosz在挑战中提出编写一个名为 memoize 的函数，该函数将一个函数作为参数并返回相同的函数。不同之处在于，这个新函数第一次被调用时，它会存储参数的结果，然后每次再次调用时都会返回此结果。
def memoize[A, B](f: A => B): A => B = ???
有没有一种纯函数式的方法来完成这个任务？
没有。就使用给定的签名和最狭义的纯函数而言，没有。
简而言之：使用可变集合即可！
g的不纯性val g = memoize(f)
// state 1
g(a)
// state 2
g(a) 会发生什么？g(a) 记忆了结果，则(内部)状态必须更改，这样在调用 g(a) 后状态与之前不同。由于这可以从外部观察到，因此对 g 的调用具有副作用，这使得您的程序是不纯的。lazy val x = 1
// state 1: x is not computed
x
// state 2: x is 1
val ll = LazyList.continually(0)
// state 1: ll = LazyList(<not computed>)
ll(0)
// state 2: ll = LazyList(0, <not computed>)
def memoize[A, B](f: A => B): A => B = {
val cache = mutable.Map.empty[A, B]
(a: A) => cache.getOrElseUpdate(a, f(a))
}
def memoizeOneValue[A, B](f: A => B)(a: A): (B, A => B) = {
val b = f(a)
val g = (v: A) => if (v == a) b else f(v)
(b, g)
}
val (b1, g) = memoizeOneValue(f, a1)
val (b2, h) = memoizeOneValue(g, a2)
// ...
f(a1) 的结果将被缓存在g中，但没有其他的。然后，您可以链接此并始终获得一个新函数。
如果您对更快的版本感兴趣，请参见@esse的答案，它执行相同的操作，但更有效率（使用不可变映射，因此为O (log(n))而不是上面的函数链表，O(n)）。
让我们尝试（注意：我已更改memoize的返回类型以存储缓存数据）：
import scala.language.existentials
type M[A, B] = A => T forSome { type T <: (B, A => T) }
def memoize[A, B](f: A => B): M[A, B] = {
import scala.collection.immutable
def withCache(cache: immutable.Map[A, B]): M[A, B] = a => cache.get(a) match {
case Some(b) => (b, withCache(cache))
case None =>
val b = f(a)
(b, withCache(cache + (a -> b)))
}
withCache(immutable.Map.empty)
}
def f(i: Int): Int = { print(s"Invoke f($i)"); i }
val (i0, m0) = memoize(f)(1) // f only invoked at first time
val (i1, m1) = m0(1)
val (i2, m2) = m1(1)
有一种纯函数式的方法来实现多态函数记忆化。这个主题非常深奥，甚至召唤了Yoneda引理，这可能是Bartosz在这个练习中所考虑的。
博客文章Memoization in Haskell通过简化问题提供了一个不错的入门：将问题限制为从整数到任意类型的函数。
下面的memoize函数接受一个类型为Int -> a的函数，并返回相同函数的记忆化版本。技巧在于将函数转换为值，因为在Haskell中，函数不能被记忆化，但是值可以被记忆化。memoize将一个函数f :: Int -> a转换成一个无限列表[a]，其中第n个元素包含f n的值。因此，当第一次访问列表的每个元素时，都会对其进行求值，并且由于惰性求值，该值会自动地被Haskell运行时缓存。
memoize :: (Int -> a) -> (Int -> a)
memoize f = (map f [0 ..] !!)
显然，这种方法可以推广到任意域的函数。关键是想出一种方法，利用域的类型作为索引，将其用于“存储”先前的值的惰性数据结构中。而这就是Yoneda引理的应用，也是我自己对这个主题的理解变得薄弱的地方。