8

我已经在 Haskell 中看到了所有其他的记忆技巧和技术，但我正在寻找的是一个在编译器/解释器级别的简单实现，它为我处理记忆。

例如，考虑斐波那契函数的以下代码：

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

我想要 ghc（或任何其他 Haskell 编译器）的某种编译器选项，默认情况下使用 memoization 执行上面的代码。例如，要计算“fib 10”，首先需要计算“fib 8”和“fib 9”。此外，计算“fib 9”取决于首先计算“fib 8”。因此，在计算“fib 10”时，我希望编译器/解释器能够理解并仅计算一次“fib 8”。

请注意，我不想编写一个新的斐波那契函数来处理记忆（就像 Haskell 中的所有其他记忆问题一样）。我想要的是保持上面的功能并且仍然有记忆。我不知道是否有任何 Haskell 编译器具有这种能力，这是我的问题的一部分。你知道可以给我这个的 Haskell 编译器吗？

谢谢

4

1 回答 1

13

编译器通常不会提供“memoize”选项，因为很难知道程序员希望在哪里以及如何执行 memoization。记忆本质上是交易时间和空间要求。

现在，如果您愿意以稍微不同的方式编写函数，那么有一种方法可以将函数的定义和使用的记忆技术解耦。

import Data.RunMemo (Memoizable, runMemo, noMemo)
import Data.MemoCombinators as Memo (integral)

fibMemoizable :: Memoizable (Integer -> Integer)
fibMemoizable recurse = go where
  go 0 = 1
  go 1 = 1
  go n = recurse (n - 1) + recurse (n - 2)

fastFib :: Integer -> Integer
fastFib = runMemo Memo.integral fibMemoizable

slowFib :: Integer -> Integer
slowFib = runMemo noMemo fibMemoizable

这使用了 Luke Palmer 的data-memocombinators包，以及我自己的玩具包runmemo。请注意，它的内容与您编写的内容相同，只是它recurse为递归调用调用。虽然这可以被集成到编译器中，但我认为没有任何理由，因为 Haskell 的表达能力足以处理这个问题，而无需编译器知道我们在做什么。

于 2012-10-25T01:00:00.320 回答