памяти бесконечных списков в Haskell

Question

Этот код используется только 1Мб ОЗУ:

main = putStrLn $ show $ length (take 2000000 [1..]) 

Хотя этот код использует 90Mb of RAM:

nums :: [Int] 
nums = nextInts 0 
    where 
    nextInts x = x : nextInts (succ x) 

main = putStrLn $ show $ length (take 2000000 nums) 

Если изменить это так, то это будет используя снова 1Мб ОЗУ:

nums :: [Int] 
nums = nextInts 0 
    where 
    nextInts x 
     |x == 90000000 = [] -- some large number 
     |otherwise = x : nextInts (succ x) 

main = putStrLn $ show $ length (take 2000000 nums) 

Вопрос: C кто-то объясняет, почему второй образец кода хранит весь список в ОЗУ, а третий не делает этого. Также опишите, как я должен изменить второй образец, чтобы использовать O (1) RAM и быть списком бесконечности.

Answer 1

Во втором случае использование памяти происходит не от хранения списка, а от создания неоцененных громкоговорителей с использованием succ x.

succ ленив, поэтому звонок succ x просто выделяет новый кусок на кучу. Этот thunk никогда не оценивается, потому что вам никогда не нужно знать значение любого из элементов списка.

В третьем случае, если вы пользуетесь x, используя защитный код x == 9000000, и поэтому трюки не растут.