这个懒惰的评估示例背后的魔力是什么？

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描述的函数

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

和主要功能

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.

如何在Haskell中使CAF不是CAF？