回忆录如何用纯函数式语言实现？

Question

纯函数的一个优点是它们的输入完全决定了它们的输出，允许缓存结果供以后使用。但是，我看不出在没有以下两种情况下如何实现：

• 可更改的全局状态来存储缓存(不可能在真正纯功能语言中实现)
• 在所有计算中线程化缓存(笨重，即使是单机计算)
• 某种带有运行时支持的注释(有点麻烦，但可能足够)
• 一个非常聪明的运行时间(可能是不可预测的，还有其他的间接费用)。

回忆录是如何在纯功能语言中普遍实现的？

Answer 1

我只是努力用纯函数的方式优化一些经常重新计算的计算(虽然我使用的语言实际上不是纯函数式)，所以我想我会分享我的发现。

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

对于我的特殊问题(重复重新计算类型信息)，我选择了使用州单的选项2，缓存内容是正在执行的状态。幸运的是，在我的示例中，所有需要缓存的函数/方法都具有相同的返回类型，因此我用新的状态monad (由原始类型和缓存组成)替换了原始返回类型。正如您所提到的，这是一个非常复杂的重构，但是最终外部界面看起来并没有太大的不同，除了不同的返回类型。

我还考虑了选项3，即将问题转移到实际函数执行之外的某种“元空间”，例如使用面向方面的编程(AOP)。我使用的是一种基于JVM的语言，所以我很好地了解了@Cacheable和其他类似的解决方案，比如jcabi-aspects。其他语言也有类似的选项，例如Python的@cached_property。这是一种非常透明的添加缓存的方法，但在我的例子中，这个解决方案与我之前所做的一些设计选择没有很好的交互(我已经使用了一个使用AOP的不同依赖注入框架，引入第二个DI解决方案可能会很复杂)。

最后，选项4是在语言实现级别上可以找到的东西。纯函数编程语言，技术上可以使用其各自的输入参数作为缓存键来缓存任何函数结果。我不知道有任何编程语言会自动这样做，但是(手动)创建回忆录函数是可以在常见的函数语言中实现的，比如Clojure和Haskell。自动完成这个任务可能很困难，因为我们必须想出一个缓存和缓存驱逐策略，为许多不同的用例场景提供时间和内存之间的合理权衡。