3

假设我有一个所有素数的列表，定义为

primes :: (Enum α, Integral α) => [α]
primes = sieve [2..]
  where sieve :: (Integral α) => [α] -> [α]
        sieve []     = undefined
        sieve (x:xs) = x : (sieve $ filter ((/= 0) . (flip mod x)) xs)

我想primes通过多个不同的功能来提供信息，例如：

sumOfPrimesLessThan :: (Integral α) => α -> α
sumOfPrimesLessThan n = sum $ takeWhile (< n) primes

或者

productOfPrimesLessThan :: (Integral α) => α -> α
productOfPrimesLessThan n = foldl (*) 1 $ takeWhile (< n) primes

或某事，好像通过做

main = do print (sumOfPrimesLessThan     1000 :: Integer)
          print (productOfPrimesLessThan 1000 :: Integer)

Haskell 会在任何时候重新计算primes或其中的任何部分吗？什么会缓存？什么不会被缓存？

附录 0：假设我有另一个函数

prime = flip elem primes

如果prime要使用不同的参数进行评估，每个评估都会重新评估primes吗？例如：

allPrime = all prime
4

1 回答 1

6

在您的情况下（对于 Haskell GHC），答案primes是重新计算。然而，如果你有一个像 一样的单态签名primes :: [Int]，那就不是这样了。这是一种调试方法：导入Debug.Trace并将trace函数添加到primes

primes :: (Enum α, Integral α) => [α]
primes = trace "call to primes" $ sieve [2..]
  where sieve :: (Integral α) => [α] -> [α]
        sieve []     = undefined
        sieve (x:xs) = x : (sieve $ filter ((/= 0) . (flip mod x)) xs)

现在，每次primes调用时，您都会看到打印出“调用素数”。编译您的程序（有或没有优化），我收到两次调用primes.

但为什么？

Haskell 实际上将您的版本编译primes为一个接受一个类型参数的函数，因此使用primesinside sumOfPrimesLessThanandproductOfPrimesLessThan实际上是一个函数调用（并且函数调用在 Haskell 中通常不会被记忆，原因很明显）。sumOfPrimesLessThan 1000 :: Integer例如，当你调用时，你实际上给了它两个参数：值1000和类型参数Integer。sumOfPrimesLessThan然后将第二个参数传递给素数。

另一方面，如果你有单态的类型签名，比如primes :: [Int], sumOfPrimesLessThan :: Int -> Int, and productOfPrimesLessThan :: Int -> Int，Haskell 编译primes成一个普通的 thunk 值，所以它只被评估一次。

这是我不久前给出的关于 Haskell 如何在内部表示值和函数的另一种解释。

SPECIALIZE编译指示（特定于 GHC）

有时您希望能够告诉 GHC，即使您的表达式是多态的，您也希望它被视为几个类型的单态。（所以你有点希望你有第二个版本primes :: [Integer]，即使在一般情况primes :: (Enum α, Integral α) => [α]下。）你可以使用SPECIALIZEpragma 指定它：

{-# SPECIALIZE primes :: [Integer] #-}
primes :: (Enum a,Integral a) => [a]
primes = ...

现在，仅针对Integer类型，primes将只计算一次。对于其他类型（如Int），我们仍然会得到与以前相同的行为。

回应附录

对于对prime = flip elem primeswhereprime是单态（“实例化”）的多次调用，您仍然只有一次调用primes. 一旦primes是单态的，它就可以在任何地方共享。另外，请注意示例中的单态限制allPrime = all prime- 您需要指定Foldablewant 的哪个实例（allPrime = all prime与 略有不同allPrime xs = all prime xs）。

于 2016-08-10T17:39:21.553 回答