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)

我想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)

哈斯克尔在任何时候都会重新计算primes,或者其中任何一部分？什么会缓存？什么不会被缓存？

附录0:假设我有另一个功能

prime = flip elem primes

如果prime要用不同的参数进行评估,每个评估会重新评估primes吗？例如:

allPrime = all prime

Answer 1

在你的情况下(对于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 sumOfPrimesLessThan并且productOfPrimesLessThan实际上是一个函数调用(并且函数调用通常不会在Haskell中被记忆,原因很明显).sumOfPrimesLessThan 1000 :: Integer例如,当你调用时,你实际上给它两个参数:value 1000和type参数Integer.sumOfPrimesLessThan然后将第二个参数传递给素数.

另一方面,如果你的类型签名是单态的,比如primes :: [Int],sumOfPrimesLessThan :: Int -> Int和productOfPrimesLessThan :: Int -> Int,Haskell只编译primes为常规的thunk值,所以它只被评估一次.

以下是Haskell如何在不久前给出的内部表示值和函数的另一种解释.

SPECIALIZE pragma(特定于GHC)

有时您希望能够告诉GHC,即使您的表达式是多态的,您也希望它被视为对于几种类型的单态.(所以你希望你有一个第二个版本,primes :: [Integer]即使一般primes :: (Enum ?, Integral ?) => [?].)你可以使用SPECIALIZEpragma 指定:

{-# 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).