Haskell中的2或3个参数的记忆/动态编程

Question

这是Haskell中一个简单的memoization,用于f1获取一个参数的函数(是的,Fibonacci):

f1 = [calc n | n <- [0..]]
     where calc 0 = 0
           calc 1 = 1
           calc n = f1 !! (n-1) + f1 !! (n-2)

现在,对于带有2个参数的函数f2,或者取3的参数f3,如何做？

对于f2,列表列表是最好的方法吗？或者可以使用不同的数据结构？

f2 = [[calc n m | n <- [0..]] | m <- [0..]]
     where calc 0 0 = 0
           calc a b = // ...something using (f2 !! a !! b)

对于f3 a b c,因为这max_a * max_b * max_c是可管理的,这个memoization /动态编程将如何工作？

我正在寻找最简单/最直接的方法,如果可能的话,使用标准的Haskell库.

编辑

正如MemoCombinators.hs克里斯泰勒的答案所示,我尝试使用v0.5.1,但它对我来说失败了,就像这样:

Could not find module `Data.IntTrie'
Use -v to see a list of the files searched for.

和

Illegal symbol '.' in type
Perhaps you intended -XRankNTypes or similar flag
to enable explicit-forall syntax: forall <tvs>. <type>

我需要这个在"普通"haskell中运行,这个版本: GHCi, version 7.6.3

任何提示,以实现目标？

Answer 1

我可以想到两种方法 -

1. MemoCombinators

创建通用 memoized函数的最简单方法可能是使用data-memocombinators库.假设您有以下两个参数函数.

f :: Int -> Int -> Integer
f 0 _ = 1
f _ 0 = 1
f a b = f (a-1) b + f a (b-1)

你可以尝试打电话f 20 20,但要准备好等一会儿.你可以轻松地编写一个memoizing版本

import Data.MemoCombinators

f :: Int -> Int -> Integer
f = memo2 integral integral f'
  where
    f' 0 _ = 1
    f' _ 0 = 1
    f' a b = f (a-1) b + f a (b-1)

请注意,在辅助函数中f',递归调用不是对f'memoized函数而是对memoized函数很重要f.f 20 20现在呼叫几乎立即返回.

2. ......的列表清单

如果您知道函数的参数是Int,并且您将需要使用全部0..n和0..m计算,f (n+1) (m+1)那么使用列表列表方法可能是有意义的.但是请注意,这与函数的参数数量有很大关系(特别是,如果你有两个以上的参数,很难一目了然地说明函数在做什么).

flist :: [[Integer]]
flist = [[f' n m | m <- [0..]] | n <- [0..]]
 where
  f' _ 0 = 1
  f' 0 _ = 1
  f' a b = flist !! (a-1) !! b + flist !! a !! (b-1)

f :: Int -> Int -> Integer
f a b = flist !! a !! b