memoize 如何在纯函数式语言中实现？

Question

纯函数的一个优点是它们的输入完全决定了它们的输出，允许将结果缓存起来以备后用。但是，我不知道如何在没有以下任何一个的情况下实现这一点：

• 存储缓存的可变全局状态（不可能在真正的纯函数式语言中）
• 通过所有计算线程化缓存（笨拙，即使使用 monad）
• 某种具有运行时支持的注释（有点hacky，但可能足够了）
• 一个非常聪明的运行时（可能是不可预测的并且有其他开销）

memoize 通常如何在纯函数式语言中实现？

Answer 1

我只是努力以纯函数式的方式优化一些经常重新计算的计算（尽管我使用的语言实际上不是纯函数式的），所以我想我应该分享我的发现。

在某种程度上，答案已经在问题中，因为它列出了所有可能的实施方法。假设使用纯函数式语言时#1 是不可能的，选项#2、#3 和#4 都是有效的可能性，并且它在一定程度上取决于通常使用哪个选项的上下文。

对于我的特定问题（重复重新计算类型信息），我选择使用State monad 的选项#2 ，其中缓存内容是正在执行的状态。幸运的是，就我而言，所有需要缓存的函数/方法都具有相同的返回类型，因此我用新的状态 monad（由原始类型和缓存组成）替换了原始返回类型。正如您所提到的，事实证明这是一次相当复杂的重构，但最终，除了返回类型不同之外，外部接口看起来并没有太大不同。

我还考虑了选项#3，即将问题转移到实际函数执行之外的某种“元空间”中，例如使用面向方面编程（AOP）。我正在使用基于 JVM 的语言，因此我仔细研究了Spring@Cacheable和其他类似的解决方案，例如jcabi-aspects. 其他语言也有类似的选项，例如 Python 的@cached_property. 这是一种非常透明的添加缓存的方式，无需进行太多更改，但就我而言，此解决方案与我之前所做的一些设计选择不能很好地交互（我已经在使用使用 AOP 的不同依赖注入框架，并且引入第二个 DI 解决方案会很复杂）。

最后，选项 #4 是在语言实现级别上可以找到的选项。纯函数式编程语言，在技术上可以使用其各自的输入参数作为缓存键来缓存任何函数结果。我不知道有任何编程语言可以自动执行此操作，但在 Clojure 和 Haskell 等常见函数语言中可以（手动）创建记忆函数。自动执行此操作可能很困难，因为必须提出一种缓存和缓存逐出策略，为许多不同的用例场景提供时间和内存之间的合理权衡。