CODEWITHSUNDEEP
haskellmemoryghclazy-evaluation
Slava Bacherikov
Slava Bacherikov

Reputation: 2066

Memory usage of infinite lists in Haskell

This code is using only 1Mb of RAM: 

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

While this code is using 90Mb of RAM:

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

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

If I change it like this, it will be using again 1Mb of RAM:

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)

Question: Can someone explain why second code sample are storing whole list in RAM, while third isn't doing it. Also describe how I should change second sample to use O(1) RAM and to be still infinity list.

Upvotes: 1

Views: 258

Answers (1)

ErikR
ErikR

Reputation: 52039

In the second case your memory usage is not coming from storing the list but from building up unevaluated thunks from the use of succ x.

succ is lazy, so calling succ x just allocates a new thunk on the heap. This thunk never gets evaluated because you never need to know the value of any of the list elements.

In the third case you are forcing the evaluation of x by using the guard x == 9000000 and therefore the thunks are not building up.

Upvotes: 13

Related Questions