haskell - Haskell 中基于 2 或 3 个参数的内存/动态编程

Question

这是 Haskell 中函数 f1 的简单内存采取一个论点(是的，斐波那契):

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是可管理的，这种内存/动态编程将如何工作？

我正在寻找最简单/最直接的方法，如果可能的话，使用标准的 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. 备忘录组合器

创建通用内存函数的最简单方法可能是使用 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 ，但要准备好等待一段时间。您可以轻松地编写一个内存版本

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'而是内存函数 f .调用f 20 20现在几乎立即返回。

2. 列表列表...

如果您知道函数的参数是 Int并且您将需要使用所有 0..n和 0..m计算 f (n+1) (m+1)那么使用列表方法可能是有意义的。但是，请注意，这与函数的参数数量严重相关(特别是，如果您有超过 2 个参数，则很难一眼看出函数在做什么)。

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