Lazy evaluation, also known as call-by-need, is an evaluation strategy where expressions are only evaluated when their values are needed. In Haskell, lazy evaluation is the default evaluation strategy, which means that expressions are not evaluated until they are required for a computation. This behavior can lead to more efficient code, as it avoids unnecessary computations and allows for infinite data structures.
Let’s illustrate lazy evaluation with an example. Consider the following Haskell function to compute the ‘n‘-th Fibonacci number:
fib :: Int -> Integer
fib n = fibs !! n
where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)The ‘fibs‘ list contains an infinite list of Fibonacci numbers computed using the ‘zipWith‘ function, which combines elements from two lists element-wise using the provided function, in this case ‘+‘. Note that ‘fibs‘ defines itself recursively by referring to itself to create the new elements in the list. This would lead to an infinite loop in a strictly evaluated language.
Now, let’s compute the 10th Fibonacci number:
main :: IO ()
main = print $ fib 10In a strict language, evaluating ‘fib 10‘ would cause the program to attempt generating the infinite list of Fibonacci numbers, which would not terminate. However, due to Haskell’s lazy evaluation, only the needed parts of the list will be computed. In this case, Haskell will only compute the first 11 Fibonacci numbers using the ‘zipWith‘ function, and then return the 10th element. The rest of the list is not computed during this process, saving time and resources.
In LaTeX format, the Fibonacci list would be defined as:
$$\begin{array}{lcl}
\mathtt{fibs} & = & [0, 1] \\
& \quad\quad & + \mathtt{zipWith} (+) \ \mathtt{fibs} \ (\mathtt{tail} \ \mathtt{fibs})
\end{array}$$
And the ‘fib‘ function would be:
fib(n) = fibs !! n