Haskell和纯函数结果的memoization

Question

可能重复:
GHC Haskell中何时自动记忆？

因此,纯函数始终为固定输入返回相同的值.也就是说,如果有足够的内存(问题1)并且开发人员对它有任何控制(问题2),Haskell(更确切地说是GHC)会自动缓存(memoize)这些结果吗？

Answer 1

我投票结束,但简短回答:

GHC不会对函数进行任何自动记忆,这可能是一件好事,因为它会使空间复杂性更难以推理.此外,memoization通常不是一个非常可解决的问题,因为它要求函数的参数具有可比性,这对于所有类型(例如,函数)实际上是不可能的.

Haskell具有非严格的语义.GHC通过需求成本模型提供或多或少的呼叫.尽管由于严格性分析器,在高优化级别下进行惰性评估的开销并不是那么糟糕.

使用延迟评估在Haskell中实现memoization非常容易.但请注意空间使用情况.

fib' :: (Integer -> Integer) -> Integer -> Integer
fib' f 0 = 0
fib' f 1 = 1
fib' f n | n > 1 = (f (n - 1)) + ((f (n - 2))

slow_fib :: Integer -> Integer
slow_fib = fib' slow_fib

fibs :: [Integer]
fibs = map (fib' memo_fib) [0..] 

memo_fib :: Integer -> Integer
memo_fib n = fibs !! n

这实际上并不是那么快,并且是一个空间泄漏,但捕获了一般的想法.您可以在Haskell维基上了解更多信息.