Question

我不明白为什么m1显然被记忆了，而m2不在下面：

m1      = ((filter odd [1..]) !!)

m2 n    = ((filter odd [1..]) !! n)

m1 10000000在第一次调用上花费大约1.5秒，在随后的调用上花费一小部分时间（大概是缓存列表），而m2 10000000总是花费相同的时间（每次调用都重建列表）。知道发生了什么事吗？关于GHC是否以及何时会记忆一个函数，有什么经验法则吗？谢谢

Answer 1

GHC不记忆功能。

然而，每次输入其周围的lambda表达式时，它最多计算代码中的任何给定表达式一次，如果它处于顶级，则最多计算一次。当您像在示例中那样使用语法糖时，确定lambda表达式的位置可能有点棘手，所以让我们将它们转换为等效的desugared语法：

m1  = (!!) (filter odd [1..])              -- NB: See below!
m2  = 
 -> (!!) (filter odd [1..]) n

（注意：Haskell 98报告实际上描述了一个类似于（a%）的左运算符部分，它等效于->；（%）a b，但GHC将其减为（%）a。这些在技术上是不同的，因为它们可以通过seq来区分。我想我可能已经提交了一份GHC-Trac关于此事的机票。）

考虑到这一点，您可以看到，在m1中，表达式filter-odd[1..]不包含在任何lambda表达式中，因此每次运行程序时只计算一次，而在m2中，每次输入lambda表达式时，即在每次调用m2时，都会计算filter odd[1../code>。这就解释了你所看到的时间上的差异。





事实上，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])


在这种情况下，新版本的效率要低得多，因为它必须从存储y的内存中读取大约1 GB，而原始版本将在恒定空间中运行，并适合处理器的缓存。事实上，根据GHC 6.12.1，在没有优化的情况下编译时，函数f的速度几乎是使用-O2编译时的两倍。

Answer 2

m1只计算一次，因为它是常数应用形式，而m2不是CAF，因此每次评估都要计算。

请参阅CAFs上的GHC wiki：http://www.haskell.org/haskellwiki/Constant_applicative_form

Answer 3

这两种形式之间有一个关键的区别：单态限制适用于m1，但不适用于m2，因为m2明确给出了自变量。所以m2s的类型是一般的，而m1s是特定的。它们被分配的类型有：

m1 :: Int -> Integer
m2 :: (Integral a) => Int -> a

大多数Haskell编译器和解释器（实际上我所知道的所有编译器和解释器）都不会记忆多态结构，所以每次调用m2的内部列表时都会重新创建它，而m1的内部列表不是。

Answer 4


我不确定，因为我自己对Haskell还很陌生，但这似乎是因为第二个函数是参数化的，而第一个函数不是。函数的本质是，它的结果取决于输入值，尤其是在函数范式中，它只取决于输入。显而易见的含义是，一个没有参数的函数总是一次又一次地返回相同的值，无论发生什么。

在GHC编译器中有一种优化机制，它利用这一事实在整个程序运行时只计算一次这样的函数的值。可以肯定的是，它做得很懒散，但还是做得很好。当我写下以下函数时，我自己也注意到了这一点：

primes = filter isPrime [2..]
    where isPrime n = null [factor | factor <- [2..n-1], factor `divides` n]
        where f `divides` n = (n `mod` f) == 0

然后为了测试它，我输入GHCI并写道：＜code＞素数！！1000。这花了几秒钟的时间，但最终我得到了答案：7927。然后我调用了＜code＞素数！！1001，并立即得到答案。类似地，在一瞬间，我得到了取1000个素数的结果，因为Haskell必须计算整个千元素列表才能返回之前的第1001个元素。

因此，如果您可以编写不需要参数的函数，那么您可能想要它。）

友情链接