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

我想挑战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()

它的工作方式与第一个版本相同。因此，它看起来像是已接受答案的证明。

最佳答案

hardwork是一个常量，在程序的顶层定义，因此一旦计算一次，便会保存其结果（就像使用main启动let hardwork = ... in ...一样）。如果您想对其进行两次计算，则可以将其定义为一个函数，并忽略第一个参数或将其用作种子，例如，将hardwork的前几行更改为

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

然后，如果您两次调用hardwork 1，则每次都会重新计算相同的列表。