這個懶惰的評估例子背後有什麼魔力？

Question

我想挑戰GHC編譯器，所以我寫了這個代碼（代碼的細節其實是不重要的，只是表明一些艱苦的工作也要做，以獲得此無限列表中的每個元素）：

hardwork :: [Int] 
hardwork = step1 where 
    -- start with value 1 
    step1 = step2 1 
    -- force the hard work being done 
    step2 i = step3 i $! step4 i 
    -- construct the current result, start next 
    step3 i result = result : step2 (i+1) 
    -- start the work with n=0 and j=1 
    step4 i = step5 i 0 1 
    -- if n=1048576, finish work and return j 
    step5 _ 1048576 j = j 
    -- otherwise increase n, and modify j 
    step5 i n j = step5 i (n+1) ((j * i) `mod` 1048575) 

現在我用的Haskellwiki

cleave :: [a] -> ([a],[a]) 
cleave = step1 where 
    step1 xs = (odds xs, evens xs) 
    odds [] = [] 
    odds [x] = [x] 
    odds (x:_:xs) = x : odds xs 
    evens [] = [] 
    evens [x] = [] 
    evens (_:x:xs) = x : evens xs 

描述的cleave功能和主要功能

main :: IO() 
main = do 
    print (take 5 (fst $ cleave hardwork), take 4 (snd $ cleave hardwork)) 

像預期的那樣，它緩慢地打印出值，因爲它必須非常努力才能得到結果。然而，令我驚訝的是，一旦拳頭清單被打印出來，第二份清單立即被計算出來。

這是一個驚喜，因爲cleave hardwork這兩個出現似乎在代碼中是不相關的，我們正在訪問它們的不同部分，看起來像一個天真的實現將再次努力工作，以獲得第二個名單。然而，GHC似乎比我想象的更加聰明。

我的問題是：他們是如何做到的？這背後的魔術是什麼？更確切地說， 運行時如何計算出一些請求值已經被評估（即使它們從未被訪問）？這種記賬是否有成本？

順便說一句，爲了確保我以正確的方式做正確的事情，我用了一種無糖，一步一步的方式來定義hardwork。有其他方法可以實現它，但如果它使用任何糖，行爲可能取決於代碼被編譯器除糖的細節。此外，這種逐步式的風格使人們更容易地手動替換表達式來進行紙質評估。

編輯

所以根據答案，我重寫hardwork，使其不CAF（這是這樣做的比回答表明反正一個更通用的方法）：

hardwork :: a -> [Int] 
hardwork = step1 where 
    step1 _ = step2 1 
    ... 

現在結果是main運行緩慢。但是，如果我用

替換 main

print (take 5 $ fst value, take 6 $ snd value) where value = cleave hardwork() 

它的工作方式與第一個版本相同。所以它看起來像是接受答案所說的一個證明。

Answer 1

hardwork是一個常量，在您的程序的頂層定義，所以一旦計算一次，它的結果將被保存（就像您已經開始main與let hardwork = ... in ...一樣）。如果你想計算了兩遍，你可以把它定義爲一個函數，要麼忽略第一個參數，或者如果你通過改變hardwork前幾行使用它作爲種子，例如

hardwork :: Int -> [Int] 
hardwork seed = step1 where 
    step1 = step2 seed 

然後兩次調用hardwork 1，每次重新計算相同的列表。

Answer 2

hardwork是一個CAF，而不是一個函數，所以它的計算結果在訪問之間沒有得到GC'd。

How to make a CAF not a CAF in Haskell?