我最近在读《程序员的范畴理论》，在其中一个挑战中，Bartosz建议编写一个名为memoize的函数，该函数将函数作为参数，并返回相同的参数，不同之处在于，第一次调用这个新函数时，它存储参数的结果，然后每次再次调用时返回该结果。
def memoize[A, B](f: A => B): A => B = ???
问题是，我想不出任何方法可以在不使用可变性的情况下实现这个函数。此外，我看到的实现使用可变的数据结构来完成任务。
我的问题是，是否有一种纯粹的功能性方式来实现这一点？也许没有可变性，或者通过使用一些函数技巧？
感谢您阅读我的问题，并感谢您今后的帮助。祝你今天愉快！
是否有一种纯功能的方法来实现这一点？
否。不是在最狭义的纯函数和使用给定签名的情况下。
TLDR：使用可变集合，没关系！
g杂质
val g = memoize(f)
// state 1
g(a)
// state 2
您预计呼叫g(a)会发生什么情况？
如果g(a)存储结果，则(内部)状态必须更改，因此调用g(a)之后的状态与之前不同。正如从外部可以观察到的那样，对g的调用有副作用，这会使您的程序变得不纯净。
从你提到的书中，2.5 Pure and Dirty Functions:
[…]函数
- 总是在给定相同输入的情况下产生相同的结果，并且
- 没有副作用
称为纯函数。
这真的是副作用吗
通常，至少在Scala中，内部状态更改不被视为副作用。
请参阅Scala Book 中的定义
纯函数是一个只依赖于其声明的输入和内部算法来产生输出的函数。它不会从"外部世界"读取任何其他值——函数范围之外的世界——也不会修改外部世界中的任何值。
以下懒惰计算的例子都会改变其内部状态，但通常仍被认为是纯粹的函数，因为它们总是产生相同的结果，并且除了内部状态之外没有副作用：
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>)
在您的情况下，等效的方法是使用私有的、可变的Map(正如您可能已经找到的实现)，比如：
def memoize[A, B](f: A => B): A => B = {
val cache = mutable.Map.empty[A, B]
(a: A) => cache.getOrElseUpdate(a, f(a))
}
请注意，缓存不是公共的。因此，对于纯函数f，如果不考虑内存消耗、定时、反射或其他有害因素，您将无法从外部判断f是被调用了两次，还是g缓存了f的结果。
从这个意义上说，副作用只是打印输出、写入公共变量、文件等。
因此，这个实现被认为是纯粹的(至少在Scala中是这样)。
避免可变集合
如果确实希望避免var和可变集合，则需要更改memoize方法的签名。这是因为，如果g不能改变内部状态，那么它在初始化后将无法存储任何新的内容。
就是一个(低效但简单)的例子
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))。
让我们试试(注意：我已经更改了内存的返回类型以存储缓存的数据)：
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在这次练习中想到的。
Haskell的博客文章Memoization通过简化问题给出了一个很好的介绍：它不考虑任意函数，而是将问题限制在整数中的函数。
下面的memory函数采用Int->类型的函数；a和返回相同函数的记忆版本。诀窍是转身将函数转换为值，因为在Haskell中，函数不是记忆化了，但价值观是。memoryize转换函数f:：Int->一其第n个元素包含f的值。因此，列表中的每个元素在第一次访问时都会进行评估并由Haskell运行时自动缓存评价
memoize :: (Int -> a) -> (Int -> a)
memoize f = (map f [0 ..] !!)
显然，该方法可以推广到任意域的函数。诀窍是想出一种方法来使用域的类型作为用于"域"的惰性数据结构的索引；存储"；以前的值。这就是Yoneda引理的由来，我自己对这个话题的理解变得脆弱。