在 Haskell 中记忆最有效的方法是什么？

Question

在 Haskell 中记住递归函数的最快方法是什么？

背景：最近我一直在用 Haskell 解决 Project Euler 问题。许多需要对递归定义的组合或数论函数进行多次计算，例如斐波那契数。如果这些函数被记忆，即函数的结果被缓存以备后用，性能会显着提高。

我见过很多解决这个问题的方法。最优雅的似乎是这个。一种使用 Data.IntMap（或哈希表）和 State monad。此答案中建议的基于树的解决方案，并且此类解决方案似乎相当普遍。再举一个例子，请参阅这篇博文。我见过使用内置函数的其他解决方案。还有一个在第2节在这里与fix，进一步似乎编译器有时可以按摩到memoizing无需额外的工作。还有几个预构建的解决方案。

我想知道对于 Project Euler 中使用的各种函数，哪种记忆方法在实践中最快。我的直觉是哈希表库，因为哈希表似乎是命令式语言中首选的字典结构。纯函数树解决方案很酷，但我的谷歌搜索告诉我，就渐近性能而言，它们比哈希表更糟糕。

编辑

一些评论说这个问题太宽泛而无法回答，经过反思，我同意。因此，让我举两个具体的函数示例进行记忆：一个函数递归计算第 n 个斐波那契数，一个函数递归计算加泰罗尼亚数。我想为大 n 多次计算这些函数。

我知道这些有明确的公式，但让我们忽略它，因为这里的真正重点是使用它们来对记忆技术进行基准测试。

Answer 1

当尝试找到第 n 个斐波那契数时，您唯一需要记住的数字是前两个数字。您可以将其作为 (f n-1, fn ) 之类的元组来执行，并在每个循环中更新此元组。请注意，更新元组是通过指针操作完成的，并且计算量并不大。

一个更干净、更聪明的替代方案是：

fibs :: [Integer]
fibs = fibcreator 0 1
  where
    fibcreator a b = a : fibcreator b (a+b)

nth = take n fibs

但我见过的最好的算法之一是：

1. 让我们定义一个矩阵 m = [e11 = 1,e12 =1,e21 = 1,e22 = 0]
2. 为了得到第 n 个斐波那契数，我们计算 m' = m ^ (n-1)
3. 矩阵 m' 中的 e11 元素是第 n 个斐波那契数

现在最棒的是，为了得到 17 个斐波那契数，我们可以这样做

m' = ((((m^2)^2)^2)^2) * m

这显着减少了计算时间并被动地将记忆嵌入算法中。重点是 Haskell 已经使用这个算法来计算幂函数，所以你不需要实现它。完整的实施是：

data Matrix = Matrix Integer Integer Integer Integer

instance Num Matrix where
  (*) (Matrix a11 a12 a21 a22) (Matrix b11 b12 b21 b22)
   = Matrix (a11*b11 + a12*b21) (a11*b12 + a12*b22) (a21*b11 + a22*b21) (a21*b12 + a22*b22)

fib4 :: Integer -> Integer
fib4 0 = 0
fib4 n = x
  where
    (Matrix x _ _ _) = Matrix 1 1 1 0 ^ (n-1)