我试图在Haskell中构建一个数据结构,函数可以使用它来避免重新计算值。例如,假设我有这样一个函数:
f :: Int -> Int -> Int
f 1 1 == 1
f m n
| abs m > n = 0
| OTHERWISE if value of f m n has already been computed by another recursive branch, return that value and add it to the "database"
| OTHERWISE return f (m-1) (n-1) + f (m - 1) n
我已经看过记忆,但还没有能够实现解决方案:
建议吗?:)
这里有一个很好的解释。
我爱memoize包:)
示例(解决"一只青蛙正在跳上楼梯…"问题):
import Data.Function.Memoize
ladder :: Integer -> Integer -> Integer
ladder n k = g n
where g = memoize f
f 0 = 1
f x = sum [g (x - y) | y <- [1..if x < k then x else k]]