将命令式记忆代码翻译成Haskell

记忆是一个有用的东西,因为它与函数密切相关,我假设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)

可以手动扩展多个参数,甚至可能是各种类型.

JavaScript解决方案最重要的是快速访问可变容器; 这些语言通常将它们作为哈希映射实现,并使它们成为一个中心语言组件(主要是因为更复杂的专用数据结构无法在虚弱类型系统中表达).

但不是在Haskell.库中有哈希映射,但也有专为备忘录设计的容器:备忘录.为什么不使用那些？

如果没有高效的容器结构,你当然也可以破解你的方式.记忆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|.

对于一个有点古怪,但非常简单的方法,使这个相当快,即Ø(√ ñ),而不是Ø(ñ):

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)