Haskell 函数定义和缓存数组

Question

我有一个关于在 Haskell 中使用数组实现缓存(内存)的问题。以下模式有效:

f = (fA !)
  where fA = listArray...

但这不是(程序的速度表明每次调用或其他东西都会重新创建数组):

f n = (fA ! n)
  where fA = listArray...

在 where 子句之外(在“全局范围”中)定义 fA 也适用于任一模式。

我希望有人能指出我对上述两种模式之间的区别的技术解释。

请注意，我使用的是最新的 GHC，我不确定这只是编译器特性还是语言本身的一部分。

编辑: !用于数组访问，所以 fA ! 5 表示 C++ 语法中的 fA[5]。我对 Haskell 的理解是 (fA !) n 将与 (fA ! n) 相同......而且对我来说，写成 "f n = fA ! n"(不带括号)会更传统。无论如何，无论我如何括号，我都会得到相同的行为。

Answer 1

Haskell 标准未指定行为差异。它所要说的是功能是相同的(在给定相同输入的情况下将产生相同的输出)。

然而，在这种情况下，有一种简单的方法可以预测大多数编译器所遵循的时间和内存性能。我再次强调这不是必需的，只是大多数编译器都会这样做。

首先将您的两个示例重写为纯 lambda 表达式，扩展该部分:

f = let fA = listArray ... in \n -> fA ! n
f' = \n -> let fA = listArray ... in fA ! n

编译器使用 let 绑定(bind)来指示共享。保证是在给定的环境中(一组局部变量，lambda body，类似的东西)，不带参数的 let 绑定(bind)的右侧最多会被评估一次。前者 fA 的环境是整个程序，因为它不在任何 lambda 下，而后者的环境较小，因为它在 lambda 下。

这意味着在后者中，可以对每个不同的 n 评估一次 fA，而在前者中这是被禁止的。

即使使用多参数函数，我们也可以看到这种模式的效果:

g x y = (a ! y) where a = [ x ^ y' | y' <- [0..] ]
g' x = (\y -> a ! y) where a = [ x ^ y' | y' <- [0..] ]

然后在:

let k = g 2 in k 100 + k 100

我们可能会多次计算 2^100，但在:

let k = g' 2 in k 100 + k 100

我们只会计算一次。

如果您正在使用 memoization，我建议在 Hackage 上使用 data-memocombinators，它是一个包含不同形状的 memo 表的库，因此您不必自己动手。