Haskell is a lazily evaluated language. The GHC-Compiler implements this semantic by evaluating expressions only as far as their result is actually needed.
In contrast to this eager evaluation always instantly and fully evaluates expressions.
In this article we will look at the advantages but also the pitfalls of laziness.
To follow this article, we assume some familiarity with the Haskell syntax as well as basic structures like lists.
There is even a german blog series on getting started in Haskell.
Laziness means, evaluating expressions as late as possible. But how does our program know, when a value needs to be evaluated and when it can (for now) be omitted?
To Evaluate or Not to Evaluate — Thunks
Even in the simplest examples, the laziness of Haskell reveals itself:
main =
let x = 5 + 3
y = error "Error"
in putStrLn (show x) -- => 8
The program runs and returns the value of the variable x. It does so even though the variable y is initialized with error "Error"?! This is because the compiler notices y never gets used. It saves on the evaluation of it and thus error never leads to an abortion of the program.
One can imagine the procedure of the GHC as follows: Every expression in our code is replaced by a placeholder. It represents a not yet evaluated expression. We call these placeholders thunks. The code basically looks like this:
main =
let x = *THUNK*
y = *THUNK*
in putStrLn (show x)
The expression putStrLn (show x) now wants to print the value of our thunk. For this however, it needs the actual value behind x… the thunk must now be evaluated and returns the result of the addition: 8.
Let‘s look at another example:
main =
let list = [error "Error", 2 + 3, 5, 6 - 1]
in putStrLn (show (length list)) -- => 4
Despite the error in the list the program runs and returns the correct result. Intuitively this is obvious: To calculate the length of a list, we can ignore the actual elements contained in it.
The Haskell compiler fulfills this intuition. At first, the list is replaced with a thunk:
main =
let list = *THUNK*
in putStrLn (show (length list))
Now, instead of fully evaluating *THUNK* (and subsequently triggering error), it only evaluates the structure of the list: list decomposes into x:xs = *THUNK* : *THUNK*. The expression length x:xs does not need the value behind x, but instead recursively returns 1 + length xs. Neither the thunk x nor any other list element ever needs to be evaluated.
We now have a basic intuition for how Haskell manages to postpone and avoid evaluating expressions, but why do we even go to the trouble of all this?
Why laziness is useful
With non-strict evaluation there are a number of advantages in developing.
Some are more obvious, while others only reveal themselves after some time.
New structures
With the by-default laziness of Haskell using recursive data structures is simple.
Whether those are infinite lists or tree structures: cunning recursive definitions allow us to define and efficiently use arbitrarily complex and nested structures.
The Sieve of Eratosthenes identifies prime numbers by removing all multiples of previously identified smaller prime numbers from a list of all natural numbers. What is left is a list of numbers without any smaller multiples, thus prime numbers. This procedure can be elegantly expressed in a single line thanks to laziness:
import Data.List.Ordered (minus, unionAll)
primes = 2 : 3 : minus [5,7..] (unionAll [[p*p, p*p+2*p..] | p <- tail primes])
The list primes is an infinite list of all prime numbers. An expression like take 100 primes now returns the first one hundred primes.
Understanding such definitions and the differently structured code they come with is not easy.
Oftentimes a new perspective on the underlying program is developed. In his paper „Why Functional Programming Matters“ John Hughes explains how lazy evaluation enables the modularization of programs. This leads us to the next topic:
Structural Rethinking
Laziness leads to another perspective onto programming itself:
A lazy language enables us to leave behind the idea of a program simply evaluating our code line by line. We simply cannot know when exactly an expression is evaluated. But as long as it has no side-effects we really don‘t care.
In this way, it gives us the freedom to think of our program as a description of some wanted result, and not just as a strict sequence of instructions.
For example, implementing the any function could be done in the following way:
any :: (a -> Bool) -> [a] -> Bool
any p xs = or $ map p xs
The definition is clear: We apply a predicate p to elements of some list xs, after that we check if at any point the predicate returned True. In a strict language this would immediately lead to a problem: The expression map p xs would be evaluated first, leading to the unnecessary evaluation of p on every list element. Even worse: Calling any on an infinite list any (>100) [1..] does not make any sense in strict evaluation. In Haskell we don‘t need to worry about any of this; lazy evaluation makes sure, the predicate p is only evaluated as often as required.
By manually implementing thunks one can obviously also implement an efficient any in a strict language, but the point is: In lazy evaluation the compiler does this task for us. Code remains efficient and clear and the expressiveness of the language increases. In fact, we don‘t need to ask ourselves if a given function does some unnecessary and avoidable computations. We can be sure that only the absolute minimum of evaluation is actually done.
These introductory examples have shown that with laziness unnecessary computation can be avoided.
In a previous german blog we built a Pretty-Printer. There, recursive function definitions and laziness were used to save hundreds of evaluations.
One could object, that experienced developers might simply eliminate those unnecessary evaluations anyways. In practice however, it is often not possible to save on evaluations by restructuring our code. When composing functions for example, eagerly evaluating the expression f . g x y must first evaluate g x y to pass the result of this to the function f. When using lazy evaluation, the thunks that appear when evaluating g x y can be passed on to f. If it turns out that the values behind these thunks are not needed further down the line, real computation was avoided.
Not always perfect - the disadvantages
Due to the delayed evaluation of our code, understanding exceptions can often be difficult. They might appear in unexpected places and require some understanding of the underlying laziness to properly debug.
Also, the space requirements of a lazy program are difficult to predict.
Over time, since expressions don‘t instantly get evaluated but instead remain as thunks, the heap can massively increase in size. With these so-called space leaks a seemingly simple calculation suddenly needs unanticipated amounts of storage.
Lastly, laziness can also make judging performance difficult.
Where in strict evaluation it is often clear, how much computation an expression causes, in Haskell this can heavily rely on how and when values are actually needed. Some optimizations that would be trivial in strict languages are suddenly no longer obvious.
Conclusion
Laziness, in a way, allows us to write programs as simple descriptions. Computations are only done when really needed. To properly use this property to write efficient code a developer must first understand when expressions really do get evaluated.
Correctly used, laziness helps in making high-performance programs with readable code. This is why it‘s one of the most elegant tools in programming Haskell.