使memoization成为Haskell的默认行为的选项

Question

我所看到的所有其他memoization的技巧和技术在Haskell,但我所寻找的是在编译器/解释的是需要照顾的memoization对我的水平直接实现.

例如,请考虑以下Fibonacci函数的代码:

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编译器吗？

谢谢

Answer 1

编译器通常不会提供"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的数据memocombinators包,以及我自己的玩具包runmemo.请注意,它的肉是一样的,你写的东西,但它调用recurse的递归调用.虽然这可以融入编译器,但我认为没有理由,因为Haskell表达足以处理这个问题,而不需要编译器知道我们正在做什么.