有没有办法在Haskell中"保留"结果？

Question

我是Haskell的新手并且理解它(基本上)是一种纯函数式语言,其优点是函数的结果不会在多次评估中发生变化.鉴于此,我很困惑为什么我不能轻易地标记一个函数,以便记住它的第一次评估的结果,并且不需要在每次需要它时再次评估它.

例如,在Mathematica中,有一个简单的习惯用于实现此目的:

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

但是在Haskell中,我发现的最接近的东西就像是

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

除了不太明确(并且显然仅限于Int参数？)之外,它(似乎)不会在交互式会话中保留结果.

不可否认(而且很清楚),我不明白到底发生了什么; 但天真地看来,Haskel似乎应该在函数定义级别上有一些方法

• 利用其功能是函数并在计算完成后跳过重新计算结果的事实,并且
• 表示希望在功能定义级别使用简单而干净的习语来完成此操作.

有没有办法在Haskell中实现这一点,我错过了？我理解(有点)Haskell不能将评估存储为"状态",但为什么不能简单地(实际上)将评估函数重新定义为它们的计算值？

---

这就产生了这个问题,缺乏这个功能会导致糟糕的表现.

Answer 1

使用合适的库,例如MemoTrie.

import Data.MemoTrie

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

这几乎不比Mathematica版本好,是吗？

关于

"为什么不能简单地(实际上)将评估的函数重新定义为它们的计算值？"

嗯,总的来说不是那么容易.这些值必须存储在某处.即使对于一个Int有价值的函数,你也不能只分配一个包含所有可能值的数组 - 它不适合内存.列表解决方案只能起作用,因为Haskell是惰性的,因此允许无限列表,但这并不是特别令人满意,因为查找是O(n).对于其他类型,它只是毫无希望 - 你需要以某种方式对一个过度可数无限的域进行对角化.

你需要一些更聪明的组织.我不知道Mathematica是如何做到这一点的,但它可能会使用很多"专有魔法".对于任何输入,我都不会确定它确实以你喜欢的方式工作.

Haskell幸运的是有类型类,这些允许你准确表达类型需要什么才能快速记忆.HasTrie就是这样一个班级.