Haskell / Frege是否会重新计算懒惰列表中的元素？ [英] Does Haskell/Frege ever recalcuate elements of a lazy list?

问题描述

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

  primes ::（Enumα，Integralα）=> ; [α] 
 primes = sieve [2 ..] 
其中sieve ::（积分α）=> [α]  - > [$] 
 sieve [] = undefined 
 sieve（x：xs）= x：（筛$ $ filter（（/ = 0）。（翻转模x））xs）
  

我想通过多个不同的函数来提供 primes ，例如：

  sumOfPrimesLessThan ::（Integralα）=> α - > α
 sumOfPrimesLessThan n = sum $ takeWhile（  

或

  productOfPrimesLessThan ::（Integralα）=> α - > α
 productOfPrimesLessThan n = foldl（*）1 $ takeWhile（< n）素数
  

或者别的什么，就好像在做



  main = do print（sumOfPrimesLessThan 1000 :: Integer）
 print（productOfPrimesLessThan 1000 :: Integer）
  

Haskell会在任何时间点重新计算素数或其任何部分？什么会缓存？什么不会被缓存？

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

  prime = flip elem primes 
  

如果 prime 将用不同的参数进行评估，每次评估都会重新评估素数？例如：

  allPrime =全部素数
  

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

  primes ::（Enumα，Integralα）=> [α] 
 primes = trace调用primes$ sieve [2 ..] 
其中sieve ::（Integralα）=> [α]  - > [$] 
 sieve [] = undefined 
 sieve（x：xs）= x：（筛$ $ filter（（/ = 0）。（翻转模x））xs）
  

现在，每次调用 primes 时，都会看到call to素数打印出来。编译你的程序（有或没有优化），我得到两个调用 primes 。

但是为什么？

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

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

此处是Haskell在不久前给出的内部值表达和值的另一种解释。
$ b

SPECIALIZE pragma（特定于GHC）

有时，您希望能够告诉GHC，即使您的表达式是多态的，您也希望它被视为单形态的一对夫妇类型。 （所以你希望你有第二个版本 primes :: [Integer] 即使一般 primes ::（Enumα，Integralα） => [α] 。）您可以使用 SPECIALIZE 杂注指定：

  { - ＃SPECIALIZE primes :: [Integer]＃ - } 
 primes ::（Enum a，Integral a）=> [a] 
 primes = ... 
  

现在，只需整数类型，素数只会计算一次。对于其他类型（比如 Int ），我们仍然会得到和以前一样的行为。

为了回应addendums

多次调用 prime = flip elem primes 其中 prime 是单形的（实例化），你仍然只有一次调用 primes 。一旦素数是单形的，它可以在任何地方共享。另外，请注意 allPrime = all prime 示例中的单态限制 - 您需要指定 Foldable 的哪个实例。希望（ allPrime =所有素数与 allPrime xs =所有素数xs ）巧妙地不同。

Suppose I have a list of all primes, defined as

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

and I want to feed primes through multiple, different functions like:

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

or

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

or something, as if by doing

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

Would Haskell, at any point in time, recalculate primes, or any part thereof? What would cached? What wouldn't be cached?

Addendum 0: Suppose I had another function

prime = flip elem primes

If prime were to be evaluated with different arguments, would each evaluation re-evaluate primes? For example:

allPrime = all prime

解决方案

In your case (for Haskell GHC) the answer is that primes is recalculated. Yet, if you had a monomorphic signature like primes :: [Int], that wouldn't be the case. Here's a way to debug this: import Debug.Trace and add the trace function to 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)

Now, every time primes is called, you will see "call to primes" printed out. Compiling your program (with or without optimizations), I get two calls to primes.

But why?

Haskell actually compiles your version of primes to a function that takes one type argument, and so the use of primes inside sumOfPrimesLessThan and productOfPrimesLessThan is actually a function call (and function calls are not in general memoized in Haskell, for pretty obvious reasons). When you call sumOfPrimesLessThan 1000 :: Integer, for example, you actually give it two arguments: the value 1000 and the type argument Integer. sumOfPrimesLessThan then passes this second argument on to primes.

On the other hand, if you had type signatures that were monomorphic, like primes :: [Int], sumOfPrimesLessThan :: Int -> Int, and productOfPrimesLessThan :: Int -> Int, Haskell compiles primes down to just a regular thunk value, so it only gets evaluated once.

Here is another explanation of how Haskell represents values and functions on the inside I gave not long ago.

SPECIALIZE pragma (specific to GHC)

Sometimes you would like to be able to tell GHC that even if your expression is polymorphic, you'd like it to be treated as monomorphic for a couple types. (So you kind of wish you had a second version primes :: [Integer] even if in general primes :: (Enum α, Integral α) => [α].) You can specify this using the SPECIALIZE pragma:

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

And now, just for the Integer type, primes will only be computed once. For other types (like Int), we will still get the same behavior as before.

In response to addendums

For multiple calls to prime = flip elem primes where prime is monomorphic ("instantiated"), you would still have only one call to primes. Once primes is monomorphic, it can be shared everywhere. Also, beware the monomorphism restriction in your allPrime = all prime example - you'll need to specify which instance of Foldable want (allPrime = all prime is subtly different from allPrime xs = all prime xs).

这篇关于Haskell / Frege是否会重新计算懒惰列表中的元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！