Menu
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 ?
793
Lazy evaluation is a method to evaluate a Haskell program. It means that expressions are not evaluated when they are bound to variables, but their evaluation is deferred until their results are needed by other computations.
Haskell is a lazy language, meaning that it employs lazy evaluation . Before explaining lazy evaluation , let's first explain strict evaluation which most readers will likely be more familiar with. Strict evaluation means that arguments to functions are evaluated prior to being passed to the functions.
Haskell uses a special form of evaluation called lazy evaluation. In lazy evaluation, no code is evaluated until it's needed. In the case of longList , none of the values in the list were needed for computation.
Haskell is a lazy language. This means that the evaluation of expressions is delayed until their values are actually needed. The opposite is eager evaluation, which is what most programming languages implement, like C, Java, and Python.
Lazy evaluation is a method to evaluate a Haskell program. It means that expressions are not evaluated when they are bound to variables, but their evaluation is deferred until their results are needed by other computations.
The Incomplete Guide to Lazy Evaluation – A series of tutorials on lazy evaluation: How it works, how it makes code more modular, how it relates to non-strict semantics, and other things. Oh my laziness! – An introduction to laziness and strictness in Haskell.
While lazy evaluation has many advantages, its main drawback is that memory usage becomes hard to predict. The thing is that while two expressions, like 2+2 :: Int and 4 :: Int, may denote the same value 4, they may have very different sizes and hence use different amounts of memory.
In consequence, arguments are not evaluated before they are passed to a function, but only when their values are actually used. Technically, lazy evaluation means call-by-name plus Sharing. A kind of opposite is eager evaluation .
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.
100
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
