評估擴展列表的頻率

是否從cumfib的每個元素的開始處開始評估fib？評估擴展列表的頻率

fib = (1:1: zipWith (+) fib (tail fib)) 
cumfib = [ sum $ take i fib | i<-[1..]]

或者是第一個i元素緩存並重新用於cumsum的元素（i + 1）？

我或多或少地猜測fib用在相同的lambda表達式中，因此僅計算一次。

此外，fib函數的實現是否對第i個斐波納契數的評估頻率有多少？我的實際問題涉及素數而不是斐波那契數，我希望「緩存」以輕鬆評估某些數n的素數因子。但是，我只使用

takeWhile (\x-> x*x<n) primes

的素數。自從我第一次和後評估小樣本的因素更大的N，的素數的增加這個子集，因此我不知道，素數是如何評估的頻次，如果我做的：

primes = ... some way of calculating primes ... 
helpHandlePrimes ... = ... using primes ... 
handlePrimes = ... using primes and helpHandlePrimes ...

請讓我知道素數是否評估一次，多次，或者這是否不能從我如何制定問題來確定。

來源

2014-03-13 Herbert

這取決於'fib'的寫入位置。它是頂級價值嗎？或者只是一個函數中的綁定變量？ – Ingo

在頂層，但我可能會這樣做：someFuntion ... = ....其中fibsOfInterest = takeWhile（<= 1000）fibs，它仍然可以工作嗎？ – Herbert

是的，fibs會根據您的需要進行擴展，而無需重新評估。 – Ingo

一個限制詞通常在其範圍內共享。特別是，在整個程序中共享模塊中的頂級術語。但是，您必須注意該術語的類型。如果這個術語是一個函數，那麼共享意味着只有lambda抽象是共享的，所以函數不會被記憶。一個過載術語在內部表示爲一個函數，因此對於過載術語，共享也是毫無意義的。

所以，如果你有一個單形態的數字列表，那麼它將被共享。默認情況下，由於「單態限制」（實際上這裏是一個有用的例子），所以你給出的列表如fib將是單形的。然而，這些天它在時尚禁用單態的限制，所以在任何情況下，我建議給一個明確的類型簽名如

fib :: [Integer]

可以肯定，使每個人都清楚，你希望這是一個單形列表。

來源

2014-03-13 09:50:37 kosmikus

我想補充一點，這樣，cumfib不必要地重新計算fib的第一個i元素的總和。它可以更有效地定義爲

cumfib = tail $ scanl (+) 0 fib

來源

2014-03-13 18:39:07

我讚賞你的評論，你是對的，但這不是我的問題的答案。 – Herbert

評估擴展列表的頻率

回答

相關問題