Lazier Than Lazy

Clojure’s lazy sequences are a great form of laziness at the language level. As a programmer, you can be even lazier by finding solutions that don’t require explicit sequence manipulation at all. You can often combine existing sequence functions to solve a problem, without having to get your hands dirty at the level of recur or lazy sequences.

As an example of this, let’s implement several solutions to the following problem. You are given a sequence of coin-toss results, where heads is :h and tails is :t:

How many times in the sequence does heads come up twice in a row? In the previous example, the answer is two. Toss 3 and toss 4 are both heads, and toss 4 and toss 5 are both heads.

The sequence of coin tosses might be very large, but it’ll be finite. Since you’re looking for a scalar answer (a count), by rule 2, it’s acceptable to use recur:

Since the purpose of the function is to count something, the loop introduces a cnt binding, initially zero on line 2. The loop also introduces its own binding for the coll, so that we can shrink the coll each time through the recur. Line 3 provides the basis for the recurrence. If a sequence of coin tosses is empty, it certainly has zero runs of two heads in a row.

Line 5 is the meat of the function, incrementing the cnt by one if the first and second items of coll are both heads (:h).

Try a few inputs to see that count-heads-pairs works as advertised:

Although count-heads-pairs works, it fails as code prose. The key notion of “two in a rowness” is obscured by the boilerplate for loop/recur. To fix this, you need to use guidelines 5 and 6, subdividing the problem to take advantage of Clojure’s sequence library.

Transforming the Input Sequence

The first problem you encounter is that almost all the sequence functions do something to each element in a sequence in turn. This doesn’t help us at all, since we want to look at each element in the context of its immediate neighbors. So, let’s transform the sequence. When you see this:

you should mentally translate that into a sequence of every adjacent pair:

Write a function named by-pairs that performs this transformation. Because the output of by-pairs varies based on the size of its input, according to rule 3, you should build this sequence lazily:

Line 3 defines a function that takes the first pair of elements from the collection. Line 5 ensures that the recursion is evaluated lazily.

Line 6 is a conditional: if the next pair doesn’t contain two elements, we must be (almost) at the end of the list, and we implicitly terminate. If we do get two elements, then on line 7, we continue building the sequence by consing our pair onto the pairs to be had from the rest of the collection.

Check that by-pairs works:

Now that we can think of the coin tosses as a sequence of pairs of results, it’s easy to describe count-heads-pairs in English:

“Count the pairs of results that are all heads.”

This English description translates directly into existing sequence library functions: “Count” is count, of course, and “that are all heads” suggests a filter:

This is much more expressive than the recur-based implementation, and it makes clear that we’re counting all the adjacent pairs of heads. But we can make things even simpler. Clojure already has a more general version of by-pairs named partition:

partition breaks a collection into chunks of size size. So, you could break a heads/tails vector into a sequence of pairs:

This isn’t quite the same as by-pairs, which yields overlapping pairs. But partition can do overlaps, too. The optional step argument determines how far partition moves down the collection before starting its next chunk. If not specified, step is the same as size. To make partition work like by-pairs, set size to 2 and set step to 1:

Another possible area of improvement is the count/filter idiom used to count the pairs that are both heads. This combination comes up often enough that it’s worth encapsulating in a count-if function:

comp is used to compose two or more functions:

The composed function is a new function that applies the rightmost function to its arguments, the next-rightmost function to that result, and so on. So, count-if will first filter and then count the results of the filter:

Finally, you can use count-if and partition to create a count-runs function that’s more general than count-heads-pairs:

count-runs is a winning combination: both simpler and more general than the previous versions of count-heads-pairs. You can use it to count pairs of heads:

But you can just as easily use it to count pairs of tails:

Or, instead of pairs, how about runs of three heads in a row?

Currying and Partial Application

If you still want to have a function named count-heads-pairs, you can implement it in terms of count-runs:

This version of count-heads-pairs builds a new function using partial:

partial performs a partial application of a function. You specify a function f and part of the argument list when you perform the partial. You specify the remainder of the argument list later, when you call the function created by partial. So, the following:

is a more expressive way of saying this:

Partial application is similar but not identical to currying.

When you curry a function, you get a new function that takes one argument and returns the original function with that one argument fixed. (Curry is named for Haskell Curry, an American logician best known for his work in combinatory logic.) If Clojure had a curry, it might be implemented like this:

One use of curry is partial application. Here is partial application in Clojure:

And here is partial application using our faux-curry:

If all you want is partial application, currying is just an intermediate step. Our faux-curry is not a real curry. A real curry would return a result, not a function of no arguments, once all the arguments were fixed. We can see the difference here, using the function true?, which takes only one argument:

Since Clojure functions can have variable-length argument lists, Clojure can’t know when all the arguments are fixed. But you, the programmer, do know when you’re done adding arguments. When you’ve curried as many arguments as you want, just invoke the function. That amounts to adding an extra set of parentheses around the earlier expression:

The absence of curry from Clojure is not a major problem, since partial is available, and that’s what people generally want out of curry anyway. In fact, some programmers use the terms currying and partial application interchangeably.

You’ve seen a lot of new forms in this section. Don’t let all the details obscure the key idea: by combining existing functions from the sequence library, you were able to create a solution that was both simpler and more general than the direct approach. And you didn’t have to worry about laziness or recursion at all. Instead, you worked at a higher level of abstraction and let Clojure deal with laziness and recursion for you.