我有一个关于在Haskell中使用数组实现缓存(memoization)的问题.以下模式有效:
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)相同......对于我来说,写一个"fn = fA!n"(没有括号)会更常规.无论如何,无论我如何括号,我都会得到相同的行为.
Haskell标准未指定行为差异.所有它必须说的是功能是相同的(在给定相同输入的情况下将产生相同的输出).
但是在这种情况下,有一种简单的方法可以预测大多数编译器所遵循的时间和内存性能.我再次强调,这不是必不可少的,只有大多数编译器都这样做.
首先将两个示例重写为纯lambda表达式,扩展部分:
f = let fA = listArray ... in \n -> fA ! n
f' = \n -> let fA = listArray ... in fA ! n
编译器使用let绑定来指示共享.保证是在给定的环境(局部变量集,lambda体,类似的东西)中,没有参数的let绑定的右侧最多将被评估一次.fA在前者的环境是整个程序,因为它不在任何lambda之下,但后者的环境因为它在lambda下而更小.
这意味着在后者中,fA 可以针对每个不同的n进行一次评估,而在前者中这是被禁止的.
即使使用多参数函数,我们也可以看到这种模式有效:
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上的数据memocombinators,它是一个不同形状的备忘表库,所以你不必自己动手.
找到正在发生的事情的最好方法是告诉编译器输出其中间表示-v4.输出很大,有点难以阅读,但应该让您准确了解生成的代码的差异,以及编译器如何到达那里.
您可能会注意到fA在第一个示例中移动到函数之外(到"全局范围").在你的第二个例子中,它可能不是(意味着它将在每次调用时重新创建).
它不被移动到函数之外的一个可能原因是因为编译器认为它取决于函数的值n.在您的工作示例,没有n为fA依靠.
但我认为编译器fA在第二个例子中避免移动的原因是因为它试图避免空间泄漏.考虑如果fA您的数组不是一个无限列表(您使用!!运算符),会发生什么.想象一下,你有大量的(例如把它称为一次f 10000),后来只用少量的(把它称为f 2,f 3,f 12...).早期调用的10000个元素仍在内存中,浪费空间.因此,为避免这种情况,fA每次调用函数时,编译器都会再次创建.
避免空间泄漏可能不会发生在你的第一个例子中,因为在那种情况下f实际上只调用一次,返回一个闭包(我们现在处于纯函数和命令世界的前沿,所以事情变得更加微妙) .这个闭包取代了原来的函数,它永远不会被再次调用,所以fA只调用一次(因此优化器可以自由地将它移到函数之外).在你的第二个例子中,f不会被闭包取代(因为它的值取决于参数),因此将再次被调用.
如果你想尝试更多地了解它(这将有助于阅读-v4输出),你可以看看Spineless无标签G-Machine纸(citeseer链接).
至于你的最后一个问题,我认为这是编译器的特点(但我可能是错的).但是,如果所有编译器都做同样的事情,即使它不是语言的一部分,也不会让我感到惊讶.