将命令式记忆代码转换为 Haskell

Question

记忆是一件有用的事情，因为它与函数密切相关，我认为Haskell有合适的机制以至少相当直接的方式实现它。

var memo = function (f) {
    var cache = {};
    return function (x) {
        if (cache[x]) return cache[x];
        else return cache[x] = f(x);
    }
}
//Usage:
var fib = memo(function (x) {
    if (x == 0) return 1;
    if (x == 1) return 1;
    return fib(x - 1) + fib(x - 2);
});
fib(100);

这是我用JavaScript编写的代码，可以做我想做的事。对Haskell来说，什么样的翻译可以提供类似的实用性和性能？

为了减少问题的歧义，我对复制JS解决方案的通用性不感兴趣，因为Haskell是强类型的。类型签名为

memo :: (Int -> b) -> (Int -> b)

可以手动扩展多个参数，甚至各种类型都可以。

Answer 1

JavaScript 解决方案的主要重要内容是一个快速访问的可变容器;这些语言通常将它们实现为哈希图，并使它们成为中心语言组件（主要是因为更复杂、更专业的数据结构无法在弱类型系统中表达）。

但不是在哈斯克尔。库中有哈希图，但也有专门为记忆而设计的容器：备忘录尝试。为什么不使用那些呢？

当然，您也可以在没有高效容器结构的情况下破解自己的方式。记忆Int ->函数的最简单方法是存储所有结果的无限列表：

memoInt :: (Int -> b) -> Int -> b
memoInt f = look
 where positives = [ f x | x <- [0..] ]
       negatives = [ f x | x <- [-1, -2 ..] ]
       look x | x<0        = negatives !! (1-x)
              | otherwise  = positives !! x

显然，列表查找对于大型|x|变得非常昂贵。

对于一个有点奇怪但非常简单的方法，即 O （√n） 而不是 O （n）：

memoInt' :: (Int -> b) -> Int -> b
memoInt' f = look
 where table = [ [ f (sqrtX^2 + dx) | dx <- [0..]    ]
                                    | sqrtX <- [0..] ]
       look x | x<0        = negDomain x
              | otherwise  = let sqrtX = floor . sqrt $ fromIntegral x
                             in table !! sqrtX !! (max 0 $ x - sqrtX)
       negDomain = memoInt' (f . negate)

（由于浮点问题，这可能会中断大量，这不是真正安全的使用sqrt）