在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库来实现最简单/最直接的方法。

编辑

正如Chris Taylor所建议的，我尝试使用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，版本7.6.3。

有什么技巧可以让它运行？

- vikingsteve

Answer 1

我可以想到两种方法 -

1. MemoCombinators

创建通用记忆化函数的最简单方法可能是使用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

- Chris Taylor

---

嗨，Chris，非常感谢你的回答，我认为我需要使用选项1，并从data-memocombinators包中提取最少量的代码，看起来我只需要type Memo和memo2，memo3，这听起来对吗？ - vikingsteve

@vikingsteve，您还需要从MemoCombinators中获取“integral”。我会查看您的错误。看起来您没有安装“data-inttrie”库。如果您运行“cabal install data-memocombinators”，它应该会自动安装，但您也可以尝试运行“cabal install data-inttrie”进行安装。这有帮助吗？ - Chris Taylor

请注意，data-memocombinators 使用了两个扩展，Rank2Types 和 ScopedTypeVariables（包描述在此处）。如果您不想依赖使用扩展的软件包，则这可能不适合您。但是，您不需要在自己的模块中启用这些扩展，因此这可能对您是可接受的。 - Chris Taylor

谢谢Chris。我想我会去读一下data-inttrie库（它似乎是一种超级高效的位运算数据结构，也许我可以用Data.Map做类似的事情？），然后使用type Memo、wrap、integral和memo2来实现我需要的自定义、“无外部库”的实现。 - vikingsteve

@vikingsteve 你也应该查看一下这个关于记忆化的页面。我使用Data.Map进行记忆化的经验是，对于具有两个以上参数的函数，很难使其正常工作，因为我无法让映射足够懒惰。但也许你会更幸运！ - Chris Taylor

只是一个补充 - 你的第二个解决方案（列表的列表）同样有效，而且更简单，不需要外部库！ - vikingsteve

Answer 2

由于Haskell是惰性的，您可以通过调用自身来记忆化函数。

例如，Haskell中的一个斐波那契生成器如下：

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

（来源：http://www.haskell.org/haskellwiki/The_Fibonacci_sequence）

使用生成的列表作为状态的存储。

- Abizern

---

好的，谢谢。我能在一个带有2或3个参数并返回一个Int的函数中使用这种惰性记忆化吗？ - vikingsteve