7. Recursion II: Lazy Sequences

Overview

In this chapter, as we continue our exploration of recursive techniques, we will focus on lazy evaluation. We will write functions that safely produce potentially infinite lazy sequences, use lazy evaluation to consume linear data, produce lazily evaluated tree structures from linear data, and write functions that consume tree structures.

By the end of this chapter, you will be able to think about new ways of understanding and solving problems.

Introduction

At its simplest, a lazy sequence is a hybrid of two things:

• A list (not a vector!) of zero or more items
• A reference to possible future items of the list that can be computed if necessary

In other words, there's a real part and a virtual part. Most of the time, you don't need to think about this distinction. That's the whole point of lazy sequences: the virtual part becomes real when you need it, if you need it. When you can stay away from the edge cases, you don't need to worry about the virtual part because as soon as it's needed, it will become real.

Over the last few chapters, we've already used lazy sequences in many different ways. They are an important, distinctive feature of Clojure and they are something that you'll use every day as a Clojure programmer. You've seen by now that they are list-like structures with a twist: while you are using the first elements of the list, the rest of the list may not...

A Simple Lazy Sequence

To start with, let's consider the simplest possible producer of lazy sequences, the range function, which simply returns a possibly infinite series of consecutive integers. The easiest way to write this is to use iterate:

(defn iterate-range [] (iterate inc 0))

Here, iterate returns a sequence that starts with the initializer value, zero, and then continues with the result of calling inc on zero, then on the result of that and so on. Each intermediate value becomes an item in the returned lazy sequence. It works just fine:

user> (take 5 (iterate-range))
(0 1 2 3 4)

The iterate function is doing all the work. We could stop here, but we wouldn't have learned much about how lazy sequences are built. Here's a more low-level version that performs the same task. It uses the lazy-seq macro, which is the base of all lazy sequences:

user> (defn our-range [n]
        (lazy-seq
   ...

Lazy Trees

So far, we've seen that the "laziness" of lazy sequences is that they can point to future computations that will only be performed if they become necessary. There is another important advantage that is equally important, and that is what we are going to explore now. Remember from Chapter 6, Recursion and Looping, how recursive functions in Clojure need to use recur to avoid blowing up the stack? And remember how recur only works with a specific kind of recursion, tail recursion, where the next call to the recursive function can totally replace the previous call? The problem, you'll recall, is that only a limited number of stack frames are available. The function call on the root node of the tree needs to wait until all the calls have completed on all the child and grandchild and great-grandchild nodes, and so on. Stack frames are a limited resource but the data we need to operate on is often vast. This mismatch is a problem.

This is where lazy evaluation...

Summary

Lazy sequences and recursion can be rather challenging. By now, you should know how to safely consume lazy sequences, how to produce them, and how to use them to build tree structures from linear data sources, all without blowing the stack of your runtime.

As we've said before, writing functions to produce your own recursion-based lazy sequences should be something that you reach for only when all the other options won't work. Start with map and filter. If that's not enough, try reduce. Maybe the other forms of recursion will work. If none of those solve your problem, you have lazy sequences, an extremely powerful and efficient tool.

Lazy sequences and recursion always make us think. Being able to write your own lazy sequences will also make you a more enlightened consumer of lazy sequences. In Clojure, this is very valuable because lazy sequences are everywhere. Techniques like the ones we've explored here can also help you start thinking about new...