Here is my attempt at explaining the case for laziness to those who aren’t already persuaded. The following contains no tedious code examples, and, I hope, appeals to principles that all developers care about. Also see my attempt at Selling Monads.
Roughly speaking, laziness is the property that expressions aren’t evaluated until required. This is useful primarily for modularity, but also sometimes efficiency.
It’s useful for modularity in the sense that it allows for a better separation of concerns. It’s one more tool in the toolkit for decomposing routines down into smaller, reusable, and more focused parts. The token toy example of this is something like writing a function that sums every integer between 0 and n. In a lazy language, one can write (1) a function that generates all natural numbers, (2) a function that only consumes as much of that sequence as is required (up to n), and (3) another function that sums the resulting stream. Compose these together, and we have a solution. It would be difficult to reproduce this in a strict language because how could you write a function that produces all natural numbers without looping forever? More likely, you would write a loop that counts up to n and sums each element in the body. So rather than decomposing the solution into three tiny reusable parts, you would end up with a single monolithic function. In a lazy language, this decomposition happens in a completely ordinary way. These are just normal functions generating and consuming normal lists. The function that produces the infinite list doesn’t cause the program to loop forever because each element is only produced when it’s demanded. It only generates as many numbers as its downstream dependencies require. Granted, something like this is possible in a strict language. In Java you might reach for an Iterator, and indeed the Iterator will solve the immediate problem. But what happens down the line when you want to use these functions with ones that operate over List rather than Iterator? Now you’re scratching your head over the Collections inheritance hierarchy and trying understand how these abstractions interact. Writing an Iterator is just fundamentally different than working with lists. With enough blood, sweat, and tears you can probably make this work, but the point is, in a lazy language this would have decomposed much more naturally.
Of course, no one is convinced by examples like this, because how often do you sum all numbers between 0 and n? And even if you did, you should probably just use the closed form formula.1
One thing to point out is that the functions described above (one for generating an infinite list, one for consuming a finite prefix of a list, and one for combining elements, perhaps into a sum) are usually part of a more general collections library. In other words, they’re useful for much more than just summing numbers.
Another objection is that strict languages can decompose the solution into reusable parts, as long as we’re willing to give up the function that produces an infinite list. Instead, we might have a function that generates a list 0 to n and another that sums the list. This is true, but note that we’re still coupling the idea of “what to generate” to the idea of “how many to generate”. So, yes, you can have modularity without laziness, but the point is laziness gives you more modularity. This is perhaps more convincing in non-toy examples. Let’s look at something more real world.
Suppose I wanted to write a retry abstraction. That is, something general that could carry out retry policies for tasks like connecting to a database, or retrying an HTTP request. In a language like Java I might write a RetryGizmo class that takes an action to retry and some parameters describing the retry policy, like time between retries, and maximum retry attempts. I might even factor those parameters out into a separate RetryPolicy class. Whenever I wanted to use it, I would create an instance of my RetryGizmo, pass in my RetryPolicy with its parameters and the action to retry.
In a lazy language, I would probably just reach for a list. Let me explain. The first thing to notice is that a retry policy is usually just a description of how long to back off between retries. This can be represented as a sequence of durations, or a list of integers, where the nth element is how long to back off before the nth retry (probably in milliseconds). If I wanted to describe an exponential back off, I would write a function that generates an infinite list of numbers, were each element is twice as large as the last element (i.e., the durations grow exponentially). This would describe a policy of retrying forever (until a success, of course), with each back off being twice the magnitude of that last. If I instead wanted finite retries, I could compose that function with a function that takes a finite prefix of that infinite list. If I want to have a maximum back off duration, I could compose that with a function that caps each element of the list at a maximum value. Most of these functions I wouldn’t have to write. In Haskell, they’re already part of the standard collections API. Finally, I would write a function that takes an action and the list that describes the retry policy. The function would consume the retry policy lazily as needed. If it only retried twice, only the first two elements would be generated and consumed. Once the retry policy list was exhausted, it would stop retrying.
So what’s happening in this example? Here, laziness allows me to separate the idea of “exponential back off” from “bounded retries” and “bounded maximum durations”, and I’m doing this all with only the lowly list. Hopefully this illustrates how the general idea of separating the generation of data from consumption of data can be useful, and how laziness enables that. Once again, you could simulate this in Java with an Iterator, but it comes much more naturally in a lazy language where lists and lazy streams collapse down into the same abstraction.
So what about efficiency? Laziness has the obvious efficiency advantage that only as much evaluation as is required is performed and then no more. Seeing how this plays out in more complex examples is actually quite fascinating. Suppose I want to know what the 3rd smallest element in a list is. I can sort the list, and then ask for the 3rd element. In a strict language, the entire list will be sorted. In a lazy language, this will only execute the sort long enough to produce the third element. Under a divide and conquer algorithm like Quicksort, only the elements that were sorted into the same division as the 3rd largest element would need to be sorted. This gives linear time rather than O(n*log n). In other words, Quicksort and Quickselect collapse into the same algorithm.
Another interesting way in which this plays out is during list processing. Suppose I define a pipeline of transformations on a list. In a language with strict lists, intermediate lists with intermediate results would be produced between each stage in the pipeline. In a lazy language, elements are instead produced one at at time. This produces intermediate allocations, but only for that one element, and these allocations are short lived.2 When I ask for the first element produced by the pipeline, each stage in the pipeline is kicked off like dominoes, but only for that first element. The tail of the list is held in suspension until I ask for the next element and so on. In Java, this would be called stream processing. In a lazy language, it’s just list processing.
So why is laziness useful? Well, it’s useful for the same reasons it’s useful in other languages! The only difference is that in a lazy language, there’s not an artificial separation between the lazy abstractions and the strict abstractions. Often, they collapse down into the same thing. That said, I’m happy to admit that it’s not a settled question. Even within the Haskell community, there’s disagreement as to whether or not laziness by default is a good idea. One downside is that it can sometimes lead to unpredictable performance. For example, you might encounter a case where some new input triggers a bit of evaluation that doesn’t normally happen and that adds a huge constant to the running time. It can also sometimes lead to excessive memory usage, as suspended computations collect in memory. If all of those computation are going to be evaluated anyway, it often makes sense to just evaluate them upfront.
That said, it’s not my aim to settle the debate on lazy vs strict, but rather to explain the case for laziness to those who aren’t already drinking the lazy kool-aid. If you’re not a Haskeller, indeed, especially if you’re not a Haskeller, I hope I’ve opened your mind up to the idea of laziness by default. If you want to learn more, Why Functional Programming Matters by John Hughes gives a much more extensive treatment of the modularity argument.3
1 Footnotes
n*(n+1)/2↩︎
Thanks to nomeata on Reddit, and others in this thread, for correcting an error in the original version of this article, which stated that laziness prevents all intermediate allocations. True list fusion would, but this isn’t true list fusion. Further, I’ve changed the wording so that it doesn’t imply only lazy languages support this.↩︎
A link to the PDF here. And a nice summary from The Morning Paper here.↩︎