Jor*_*dan 106 haskell memoization ghc
我无法弄清楚为什么m1显然被记忆,而m2不在下面:
m1 = ((filter odd [1..]) !!)
m2 n = ((filter odd [1..]) !! n)
m1 10000000在第一次调用时大约需要1.5秒,而后续调用需要一小部分(大概是缓存列表),而m2 10000000总是花费相同的时间(每次调用重建列表).知道发生了什么事吗？关于GHC是否以及何时会记忆功能,是否有任何经验法则？谢谢.
Rei*_*ton 111
GHC不会记忆功能.
但是,它确实在每次输入其周围的lambda表达式时计算代码中的任何给定表达式,或者如果它处于最高级别,则至多计算一次.当你在你的例子中使用语法糖时,确定lambda表达式的位置可能有点棘手,所以让我们将它们转换为等效的desugared语法:
m1' = (!!) (filter odd [1..]) -- NB: See below!
m2' = \n -> (!!) (filter odd [1..]) n
(注意:Haskell 98报告实际上描述了一个左边的操作符部分,但是GHC将其(a %)视为等同于.这些在技术上是不同的,因为它们可以区分.我想我可能已经提交了GHC Trac票据.)\b -> (%) a b(%) aseq
鉴于此,您可以看到,m1'表达式filter odd [1..]不包含在任何lambda表达式中,因此每次运行程序时只会计算一次,而in m2',filter odd [1..]每次输入lambda表达式时都会计算,即每次打电话m2'.这解释了你所看到的时间差异.
实际上,某些版本的GHC具有某些优化选项,将分享比上述描述更多的值.在某些情况下,这可能会有问题.例如,考虑一下这个功能
f = \x -> let y = [1..30000000] in foldl' (+) 0 (y ++ [x])
GHC可能会注意到y不依赖x和重写函数
f = let y = [1..30000000] in \x -> foldl' (+) 0 (y ++ [x])
在这种情况下,新版本的效率要低得多,因为它必须从存储器的内存中读取大约1 GB y,而原始版本将在恒定的空间中运行并适合处理器的缓存.实际上,根据GHC 6.12.1,在没有优化的情况下编译f时,函数的速度几乎是编译时的两倍.-O2
scl*_*clv 28
m1仅计算一次,因为它是常量应用形式,而m2不是CAF,因此为每个评估计算.
请参阅CAF上的GHC wiki:http://www.haskell.org/haskellwiki/Constant_applicative_form
mok*_*kus 13
两种形式之间存在着重要的区别:单态限制适用于m1但不适用于m2,因为m2已经明确给出了参数.所以m2的类型是通用的,但m1是特定的.他们分配的类型是:
m1 :: Int -> Integer
m2 :: (Integral a) => Int -> a
大多数Haskell编译器和解释器(我实际上都知道它们)不会记忆多态结构,因此每次调用m2时都会重新创建m2的内部列表,其中m1不是.