Haskell的懶惰是Python生成器的優雅替代品嗎？

Question

在編程練習中，首先要求對階乘函數進行編程，然後計算和：1! + 2! + 3! +... n!,O(n)乘法（因此我們不能直接使用階乘）。我不是在尋找解決這個特定（微不足道）問題的方法，我試圖探索Haskell的能力，這個問題是我想玩的玩具。

我認爲Python的生成器可能是這個問題的一個很好的解決方案。例如：

from itertools import islice 
def ifact(): 
    i , f = 1, 1 
    yield 1 
    while True: 
     f *= i 
     i += 1 
     yield f 

def sum_fact(n): 
    return sum(islice(ifact(),5)) 

然後我試圖找出是否有東西在Haskell比該發生器類似的行爲，我認爲懶惰做所有的工作人員沒有任何額外的概念。

例如，我們可以用

fact = scan1 (*) [1..] 

取代我的Python ifact進而解決行使如下：

sum n = foldl1 (+) (take n fact) 

我不知道如果這個解決方案是真正的「等效」 Python的一個關於時間複雜度和內存使用。我會說Haskell的解決方案從不存儲所有列表的事實，因爲它們的元素只被使用一次。

我是對的還是完全錯的？

---

編輯： 我應該檢查更精確：

Prelude> foldl1 (+) (take 4 fact) 
33 
Prelude> :sprint fact 
fact = 1 : 2 : 6 : 24 : _ 

所以（我的執行）哈斯克爾存儲結果，即使它不再使用。

Answer 1

您的示例是而不是等效於內存使用情況。很容易看出你是否用+替換*（以便數字不會太大），然後在諸如10^7的大n上運行這兩個示例。你的Haskell版本會消耗大量的內存，而python會保持低版本。

Python生成器不會生成值列表，然後總結它。相反，sum函數將從發生器逐個獲取值並累積它們。因此，內存使用量將保持不變。

Haskell會懶懶地評估函數，但爲了計算說foldl1 (+) (take n fact)它將不得不評估完整的表達式。對於大型n這將展開成一個巨大的表達，就像(foldl (+) 0 [0..n])一樣。有關評估和減少的更多細節，請看這裏：https://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27。

您可以通過使用foldl1'而不是foldl1修復您的sum n，如上面鏈接中所述。正如@ user2407038在他的評論中解釋的那樣，你還需要在本地保留fact。在GHC下面的作品以恆定的內存使用：

let notfact = scanl1 (+) [1..] 
let n = 20000000 
let res = foldl' (+) 0 (take n notfact) 

注意的是，在地方notfact內存考慮實際的階乘的情況下是不太關心的。數字會很快變大，任意精度算術會減慢速度，所以你將無法獲得大數值n以便真正看到差異。

Answer 2

基本上，是的：如果這些生成器毫不費力地克隆，緩存和合成，Haskell的懶惰列表就像Python的生成器一樣。您可以從遞歸函數返回[]來代替StopIteration，遞歸函數可以將狀態線程化爲生成器。

由於自遞歸，他們做了一些更酷的東西。

facts = 1 : zipWith (*) facts [1..] 

或Fibonaccis爲：：例如，你的階乘發生器更慣用等產生

fibs = 1 : 1 : zipWith (+) fibs (tail fibs) 

一般而言任何迭代循環可以通過促進循環狀態轉換爲遞歸算法函數的參數，然後遞歸地調用它來獲得下一個循環。生成器就像那樣，但是我們在遞歸函數的每次迭代前加上一些元素，'go ____ =（stuff）：go ____。因此

完美的等效是：

ifact :: [Integer] 
ifact = go 1 1 
    where go f i = f : go (f * i) (i + 1) 

sum_fact n = sum (take n ifact) 

在一個什麼樣的速度最快的方面，在Haskell的絕對速度最快的將可能是個「for循環」：

sum_fact n = go 1 1 1 
    where go acc fact i 
      | i <= n = go (acc + fact) (fact * i) (i + 1) 
      | otherwise = acc 

事實上，這是「尾部遞歸「（go的調用不會將任何子調用管理到go到(+)或(*)等其他功能）意味着編譯器可以將它打包成一個非常緊密的循環，這就是爲什麼我將它與」 for循環「，儘管這對Haskell來說不是一個真正的本地想法。

以上sum_fact n = sum (take n ifact)比這慢一點，但比sum (take n facts)快，其中facts是用zipWith定義的。速度差異不是很大，我認爲大多數情況下只是歸結爲內存分配，不能再次使用。

Answer 3

事實上，懶惰列表可以這樣使用。雖然有一些細微的差異：

• 列表是數據結構。所以你可以在對它們進行評估之後保留它們，這可以是好的也可以是不好的（你可以避免重新計算值和像@ChrisDrost描述的遞歸技巧，代價是保持內存不被釋放）。
• 列表是純的。在發電機中你可以計算副作用，你不能用列表來做這件事（這是經常需要的）。
• 由於Haskell是一種懶惰的語言，懶惰無處不在，如果您只是將一個程序從命令式語言轉換爲Haskell，內存需求可能會發生相當大的變化（如@RomanL在他的回答中所述）。

但Haskell提供更先進的工具來完成發電機/消費者模式。目前有三個庫專注於此問題：pipes, conduit and iteratees。我最喜歡的是conduit，它很容易使用，其類型的複雜性保持較低。

它們有幾個優點，特別是您可以創建複雜的管道，並且可以將它們基於選定的monad，這允許您說出管道中允許的副作用。

import Data.Functor.Identity 
import Data.Conduit 
import qualified Data.Conduit.List as C 

ifactC :: (Num a, Monad m) => Producer m a 
ifactC = loop 1 1 
    where 
    loop r n = let r' = r * n 
       in yield r' >> loop r' (n + 1) 

sumC :: (Num a, Monad m) => Consumer a m a 
sumC = C.fold (+) 0 

main :: IO() 
main = (print . runIdentity) (ifactC $= C.isolate 5 $$ sumC) 
-- alternatively running the pipeline in IO monad directly: 
-- main = (ifactC $= C.isolate 5 $$ sumC) >>= print 

在這裏，我們創建產生階乘無限期Producer（即不消耗輸入管道）：

使用導管，如下的例子可以表達。然後我們用isolate來組合它，它確保不超過給定數量的值通過它傳播，然後我們用一個Consumer組合它，它只是求和值並返回結果。