有没有一种方法可以在Haskell中“保留”结果？

Question

有没有一种方法可以在Haskell中“保留”结果？

haskellfunctional-programmingmemoization

5

我刚开始学习 Haskell，了解到它基本上是一种纯函数式语言，这有一个优点，即函数的结果在多次计算中不会改变。鉴于此，我对为什么不能轻松地标记一个函数，以便它记住其第一次计算的结果，并且每次需要其值时不必重新计算感到困惑。

例如，在 Mathematica 中，有一个简单的习惯用法可以实现这个功能：

f[x_]:=f[x]= ...

但是在Haskell中，我发现最接近的东西类似于某些东西。

f' = (map f [0 ..] !!)
   where f 0 = ... 
         f n = f' ...

除了不太清晰（并且显然仅限于Int参数？），它似乎不能在交互会话中保留结果。

必须承认（并且很明显），我不完全理解这里发生了什么；但是天真地说，Haskel似乎应该有一种方法，在函数定义级别利用其函数的“函数性质”，一旦计算出结果就跳过其结果的重新计算，并以简单干净的方式表达对此的愿望。

有没有办法在Haskell中实现这一点？我有点明白Haskell不能将评估结果存储为“状态”，但是为什么它不能简单地（实际上）重新定义已评估的函数为它们的计算值呢？

这是从这个问题中发展而来的，其中缺乏这个功能导致了可怕的性能问题。

- orome

GHC 已经决定，如果您记住函数应用程序，那么您可能会使用太多内存，而它可能是正确的。不过，它确实记住常量。 - PyRulez

1

如果愿意的话，另一个Haskell实现可以自由地对函数进行记忆化。 - PyRulez

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- leftaroundabout · Accepted Answer

使用适当的库，例如MemoTrie。

import Data.MemoTrie

f' = memo f
 where f 0 = ... 
       f n = f' ...

这几乎和Mathematica的版本一样好，不是吗？

关于：

“为什么不能简单地（实际上）重新定义已评估函数为其计算值呢？”

嗯，在一般情况下并不容易。这些值必须存储在某个地方。即使对于一个返回Int类型值的函数，你也不能只是分配一个包含所有可能值的数组 - 它不会适应内存。列表解决方案之所以可行，是因为Haskell是惰性的，因此允许无限的列表，但这并不是特别令人满意，因为查找的复杂度是O(n)。对于其他类型来说，这就根本是绝望的了 - 你需要以某种方式对称化一个超可数无限域。

你需要一些更聪明的组织方式。我不知道Mathematica是如何做到这一点的，但它可能使用了很多“专有魔法”。我不这么肯定它是否真的按照你希望的方式工作，对于任何输入。

幸运的是，Haskell有类型类，这允许你精确表达类型需要什么才能快速地进行记忆化。 HasTrie就是这样一个类型类。