Don't be lazy about lazy sequences.

Posted by Uncle Bob on 08/06/2009

Coding with infinite sequences is very powerful, but also very bizarre. If you aren’t careful you can get algorithms that work fine, but are O(N^2) instead of O(N).

Consider the (partial-sums) function that I used in my previous blog on generating pi.

(defn partial-sums [s]   (lazy-seq     (cons (first s) (add-streams (next s) (partial-sums s)))))

This function takes in a list of (a b c…) and returns a list of partial sums (a a+b a+b+c…). Trying to figure out how this function works is a bit mind-bending; at least for me; but here’s how I visualize it.

It adds (next s) to (partial-sums s).

                  (next s)                       |                       V               s: (a   b    c     d ...) (partial-sum s):     (a   a+b  a+b+c ...)

Notice how the vertical columns are the sums that we want. Notice also that each result is the sum of the previous result and the next element of s. So verbally and visually this all makes sense. But algorithmically it can still be challenging to understand. I mean, how do those values get calculated really?

Oh… And I should note… The function above doesn’t work this way at all. It’s actually horrifically inefficient. But I’ll get to that, and to the solution. First things first.

What allows this function to run is lazy-evaluation. All that really means is that an element of a list does not really exist until you ask for it. At that point the program calculates what the element of the list should be and then returns it to you as if it was there all along.

In Clojure, when you build a sequence inside the (lazy-seq) form, it simply defers the execution of the procedures that generate the values of the sequence until those values are requested. Look again at the function above. When you call it, it simply returns immediately without doing anything. The (lazy-seq) form simply short-circuits the execution of the function, deferring it for later.

So when (partial-sums) returns it gives you a sequence, but there’s nothing in it! However, as soon as you ask for the first element, the body of the (partial-sums) function will execute just enough to give you the value of the first element. No other elements are calculated. When you ask for the next value, (partial-sums) will execute again, just enough to give you that value. And so on.

Knowing that, let’s trace the execution.

• • We call (partial-sums s) which returns a list (let’s call it ps)

  • To get the first element of ps, (partial-sums) is lazily-invoked and simply returns (first s)

  • For the second element it returns the first element of the sequence produced by (add-streams (next s) (partial-sums s))

  • which will be: (+ (first (next s)) (first s))

  • For the third element it returns the second element of the added streams, but the element is composed of yet another stream addition invoked by the recursive (partial-sums) So it looks like this:

  • (+ (first (next (next s)) (+ (first (next s)) (first s))

“Uh… Wait.” I hear you say. “You mean that in order to calculate the third element, you have to add three elements? Didn’t we say that we could add the next element of s to the previous element of the partial sums? Why do we have to do three additions? Why does it seem to be doing this:”

(a b c)   (a b c)     (a b c)

Notice that the vertical columns are the sums we are looking for; but calculating them requires a lot more work than just adding the next value to the previous sum!.

“But wait,” you say again. “I know something about Clojure. Clojure memoizes the list values. Once you ask for a list element the first time, it never has to recalculate it again! So when we get the third element of the result it shouldn’t have to recalculate the second.”

Partly right. Once you lazily evaluate a list element, that element never has to be evaluated again. It’s in the list, and will simply be returned from the list. But let me ask you this: In the function above, where is the list that being asked again? Look closely. There is no partial-sums result that is being asked for a value more than once. Indeed, every time we need a value we create a new (partial-sums) list. So we aren’t taking advantage of the previous values because we’re always creating a new list.

If you’d like to prove this to yourself, you can run this fun little program.

(defn p [a b] (println a '+ b) (+ a b))  (defn add_streams [a b] (map p a b))  (defn partial-sums [s]     (lazy-seq       (cons (first s)         (add_streams (next s) (partial-sums s)))))  (def w (iterate inc 1)) (println (take 5 (partial-sums w)))

Notice how I print every addition in the (p) function. If you run this you’ll get the following result:

(2 + 1 1 2 + 1 3 + 3 3 2 + 1 3 + 3 4 + 6 6 2 + 1 3 + 3 4 + 6 5 + 10 10 15)

The jumble of numbers is evidence that the lazy evaluation is working. As the println marches through the 5 partial sums, it causes each to be evaluated, causing each sum to be printed. Notice how many sums are taken! Ten additions for 5 partial sums. It’ll be 15 for 6, and 21 for 7. Indeed, the number of additions required to calculate ps[n] is equal to ps[n-1]. A little thought will convince you that this is O(n^2).

To reduce this back to O(n), we need to stop creating a new list of partial-sums at each recursion, and use a single copy of the partial-sums result. We can do this by saving the partial sums result in a var, and then using that in the add-streams call.

(defn partial-sums [s]     (def result (lazy-seq       (cons (first s)         (add_streams (next s) result)))) result)

This may bend your brain just a little bit more. We are using the result before we are done calculating it! But that’s ok, since we never use more than has already been calculated…

Running the program with this change yields the following output.

(2 + 1 1 3 + 3 3 4 + 6 6 5 + 10 10 15)

That’s the O(n) behavior we wanted! Each sum is calculated by adding the next element to the previous sum! Hooray!

There’s a lesson here. You don’t get the benefit of lazy sequences unless you use the lazy sequences. Creating a brand new one each time may generate the right answer, but it’s lazy, and can burn a lot of execution cycles.

One problem I have with this solution is the creation of the global var ‘result’. I’m sure there’s a way to create a local result; but I haven’t found it yet. (I tried using various let forms, but I haven’t stumbled upon one that works yet.)

Comments

Leave a response