Какая магия этого ленивого примера?

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) 

Теперь я использую функцию cleave, описанную в 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 

и основные функции

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

Как и ожидалось, он медленно печатает значения, поскольку для получения результатов требуется очень тяжелая работа. Однако меня удивляет, что после распечатки первого списка второй список был рассчитан немедленно.

Это неожиданность, потому что два случая cleave hardwork, по-видимому, не связаны в коде, и мы обращаемся к их разной части, это похоже на наивную реализацию, которая снова сделает тяжелую работу, чтобы получить вторую список. Однако GHC кажется умнее, чем я думаю.

Мой вопрос: как им это удалось? Какая магия позади этого? Точнее, как время выполнения вычисляет некоторое запрошенное значение уже было оценено (даже если они никогда не были доступны)? Существуют ли какие-либо затраты для такого рода бухгалтерского учета?

BTW, чтобы убедиться, что я правильно делаю правильный путь, я использовал неослабевающий шаг за шагом, чтобы определить hardwork. Существуют другие способы его реализации, но если он использует любые сахара, поведение может зависеть от того, как компилятор будет дезагрегирован. Кроме того, этот пошаговый стиль облегчает оценку бумаги с помощью удобных замен.

EDIT

Итак, в соответствии с ответами, я переписал 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?