108

我无法弄清楚为什么 m1 显然被记住了，而 m2 不在以下内容中：

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

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

m1 10000000 在第一次调用时大约需要 1.5 秒，而在后续调用中只需要一小部分时间（大概它会缓存列表），而 m2 10000000 总是需要相同的时间（每次调用都重建列表）。知道发生了什么吗？关于 GHC 是否以及何时会记忆功能是否有任何经验法则？谢谢。

4

4 回答 4

115

GHC 不记忆函数。

但是，它确实在每次输入其周围的 lambda 表达式时最多计算一次代码中的任何给定表达式，或者如果它位于顶层，则最多计算一次。当您在示例中使用语法糖时，确定 lambda 表达式的位置可能有点棘手，因此让我们将它们转换为等效的脱糖语法：

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

（注意：Haskell 98 报告实际上描述了一个左操作符部分，(a %)如等价于\b -> (%) a b，但 GHC 将其脱糖为(%) a。这些在技术上是不同的，因为它们可以通过 来区分seq。我想我可能已经提交了一份 GHC Trac 票。）

鉴于此，您可以看到 in 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

于 2010-10-16T22:30:26.797 回答
30

m1 只计算一次，因为它是一个常量应用形式，而 m2 不是 CAF，因此每次计算都会计算。

请参阅有关 CAF 的 GHC wiki：http ://www.haskell.org/haskellwiki/Constant_applicative_form

于 2010-10-16T22:43:09.393 回答
15

这两种形式之间有一个关键的区别：单态限制适用于 m1 但不适用于 m2，因为 m2 已明确给出参数。所以 m2 的类型是通用的，但 m1 的类型是特定的。它们被分配的类型是：

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

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

于 2010-10-18T13:55:09.853 回答
1

我不确定，因为我自己对 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并写道：primes !! 1000. 花了几秒钟，但最终我得到了答案：7927。然后我打电话primes !! 1001并立即得到了答复。同样，我很快就得到了 的结果take 1000 primes，因为 Haskell 必须计算整个千元素列表才能返回第 1001 个元素。

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

于 2013-11-02T15:41:46.980 回答