Does Haskell discards intermediary results during lazy evaluation?

user_1620367 0
Viewed 100

If I define the Fibonacci sequence recursively:

fibo_lazy_list = 0 : 1 : zipWith (+) fibo_lazy_list (tail fibo_lazy_list)

Then ask for the first element above a given value, say:

print $ find (>100) fibo_lazy_list

I understand that Haskell evaluates only the elements which are required to get the printed results. But are they all kept in memory until the print ? Since only two elements of the list are required to compute the last one, does Haskell release the left-most elements or does the list keep growing in memory ?

lazy-sequences lazy-evaluation haskell
1 Answers

It depends.

This is actually one of the most tricky things to get right for real-world Haskell code: to avoid memory leaks caused by holding on to unnecessary data, that was only supposed to be intermediary but turns out to be actually a dependency to some yet-unevaluated lazy thunk, and therefore can't be garbage-collected.

In your example, the leading elements of fibo_lazy_list (BTW, please use camelCase, not underscore_case in Haskell) will not be garbage-collected as long as fibo_lazy_list is refered by something that could still be evaluated. But as soon as it goes out of scope, that isn't possible. So if you write it like this

print $ let fibo_lazy_list = 0 : 1 : zipWith (+) fibo_lazy_list (tail fibo_lazy_list)
        in find (>100) fibo_lazy_list

then you can be pretty confident that the unused elements will be garbage collected, possibly before the one to be printed is even found.

If however fibo_lazy_list is defined at the top-level, and is a CAF (as it will be if the type is not polymorphic)

fiboLazyList :: [Integer]
fiboLazyList = 0 : 1 : zipWith (+) fiboLazyList (tail fiboLazyList)

main :: IO ()
main = do
   ...
   print $ find (>100) fiboLazyList
   ...

then you should better expect all the leading elements to stay in memory even after the >100 one has been extracted.

Compiler optimisation may come in helpful here, so can strictness annotations. But as I said, this is a bit of a pain in Haskell.

user_7459030
Related