haskell - Haskell/Frege 是否曾经重新计算惰性列表的元素？

Question

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

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

我想通过多个不同的函数提供素数，例如:

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 会在任何时间点重新计算素数或其任何部分吗？会缓存什么？什么不会被缓存？

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

prime = flip elem primes

如果使用不同的参数评估 prime，每次评估是否都会重新评估 primes？例如:

allPrime = all prime

Answer 1

就你的情况(对于 Haskell GHC)来说，答案是 primes被重新计算。然而，如果你有一个像 primes :: [Int] 这样的单态签名，事实并非如此。这是调试此问题的方法: import 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被调用时，您将看到打印出“call to primes”。编译您的程序(有或没有优化)，我收到两次对 primes 的调用.

但是为什么呢？

Haskell 实际上编译了你的 primes 版本到一个采用一种类型参数的函数，因此使用 primes里面sumOfPrimesLessThan和productOfPrimesLessThan实际上是一个函数调用(由于非常明显的原因，函数调用在 Haskell 中通常不会被内存)。当您调用sumOfPrimesLessThan 1000 :: Integer时，例如，您实际上给它两个参数:值 1000和类型参数 Integer 。 sumOfPrimesLessThan然后将第二个参数传递给素数。

另一方面，如果您有单态的类型签名，例如 primes :: [Int] , sumOfPrimesLessThan :: Int -> Int ，和productOfPrimesLessThan :: Int -> Int , Haskell 编译 primes降到只是一个常规的 thunk 值，因此它只被评估一次。

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

SPECIALIZE pragma(特定于 GHC)

有时您希望能够告诉 GHC，即使您的表达式是多态的，您也希望将其视为几种类型的单态。 (所以你有点希望你有第二个版本 primes :: [Integer] 即使一般来说 primes :: (Enum α, Integral α) => [α] 。)你可以使用 SPECIALIZE 来指定它编译指示:

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

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

回应附录

多次调用prime = flip elem primes哪里prime是单态的(“实例化”)，您仍然只能调用一次 primes 。一次primes是单态的，可以在任何地方共享。另外，请注意 allPrime = all prime 中的单态限制。示例 - 您需要指定 Foldable 的哪个实例想要( allPrime = all prime 与 allPrime xs = all prime xs 略有不同)。