Daily Archives: February 9, 2012

The for macro in Clojure

Although, strictly speaking, Clojure doesn’t have a ‘for’ loop in the sense of imperative languages like Java and C#, it does have a ‘for’ macro which provides, if anything, more functionality than the traditional ‘for’ loop. We’ll look at a few examples here.

The easiest way to get a feel for what for does is to look at a very simple example:

```(defn squares-list [n]
(for [i (range 1 (inc n))]
(* i i)))
```

The first argument to for is a vector. Entries in the vector come in pairs. The first element in each pair is a symbol, and the second element is a list. for will bind the symbol to each element in the list in turn, and then execute the body of the for, which is the second argument to the for statement, and in the example given, is (* i i). In this example, then, the symbol i is bound to each number from 1 to n in turn, and for each such i, its square is calculated. The for returns a list of all the results it calculates, so in this case, we would get a list containing the squares of all the numbers from 1 to n.

```=>(squares-list 5)
(1 4 9 16 25)
```

Nested for loops in imperative languages are easy to implement in Clojure as well. For example

```(defn sum-of-squares [n]
(for [x (range 1 (inc n))
y (range (inc x) (inc n))]
(+ (* x x) (* y y))))
```

The first pair in the vector lets x range over values from 1 to n. For each value of x, y then ranges over values from x+1 to n. The body of the for then calculates x^2 + y^2, and the final result is a list of all such values. For example

```=> (sum-of-squares 5)
(5 10 17 26 13 20 29 25 34 41)
```

The elements in the result are 1*1+2*2, 1*1+3*3, 1*1+4*4, 1*1+5*5, 2*2+3*3 and so on.

At this stage, a single for in Clojure can be seen to be about as powerful as a traditional for, nested to any level we want. However, the Clojure for offers even more options, since each binding in the first argument vector can have one or more modifiers attached to it. We’ll look at a slightly more involved example to see how these modifiers work.

Suppose we want a list of all prime numbers less than a certain integer n. Remember that a prime number is one that is divisible only by 1 and itself. In order to generate the required list, we first need to be able to test whether a given number is prime. There are various ways this can be done, but a straightforward way is to try dividing the number by all numbers from 2 up to the number’s square root, since if it has any divisors, at least one of them must be less than or equal to the square root. We can do this in Clojure as follows.

```(defn prime? [n]
(let [denoms (range 2 (inc (int (Math/sqrt n))))
zero-rems (filter #(zero? (rem n %)) denoms)]
(zero? (count zero-rems))))
```

We use a let to define two lists. The first list, denoms, is a list of numbers from 2 to the greatest integer less than or equal to the square root. The notation Math/sqrt calls the Java sqrt() function in the Math class, which returns a double. The Clojure int function takes the integer part of a double.

The second list uses filter, which we saw earlier, to find all the numbers in denoms that divide n evenly (that is, with zero remainder). Recall that filter takes two arguments: the first is a unary predicate function (one that takes a single argument and returns true or false), and the second is a list of values which are applied one at a time to the predicate.

In this case, we’ve used an anonymous function as the predicate. The Clojure notation for an anonymous function is the hash sign # followed by a function body in parentheses. Arguments to the function are represented by the percent sign % followed by a number. Thus %1 refers to the first argument, %2 to the second and so on. A bare % without a number after it, as we’ve used here, also refers to the first argument. Thus the anonymous function here calculates the remainder when n is divided by its argument, and then tests if that remainder is zero.

The final line of prime? counts the number of elements in zero-rems and tests if that value is zero. If so, that means than no numbers divide n, so n must be prime.

With prime? defined, we can now look at finding all primes less than a given value. The code is

```(defn primes-less-than [n]
(for [x (range 2 (inc n))
:when (prime? x)]
x))
```

Here, x ranges from 2 to n, but this time there is a modifier in the form of a :when clause. This means that, for the current value of x, execution will continue past that point only when the :when condition is true. In this case, that means that execution will continue only when x is prime. If the :when condition isn’t true, all further code for that value of x is skipped, and the next value of x is obtained.

Running this example, we get

```=> (primes-less-than 50)
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)
```

With nested fors, each binding can have its own modifiers. As a somewhat contrived example, consider

```(defn triples-for-primes [n]
(for [x (range 2 (inc n))
y (range (inc x) (inc n))
:when (prime? (+ x y))
z (range (inc y) (inc n))
:when (prime? (+ x y z))]
(list x y z)))
```

This function will find all triples such that the sum of the first two numbers and the sum of all three numbers are both primes. This is a triply-nested loop, with x ranging from 2 to n, y from x+1 to n, and z from y+1 to n. For given values of x and y, values of z will be considered only if x+y is prime. If it isn’t, then everything after that point is skipped, and the next value of y is obtained.

The :when condition on z means that the body of the for (the ‘list’ statement) is run only if x+y+z is prime. The result is we get a list of all triples that satisfy both conditions. For example

```=> (triples-for-primes 8)
((2 3 6) (2 3 8) (2 5 6) (3 4 6) (4 7 8) (5 6 8))
```

We see that 2+3 and 2+3+6 are both prime in the first triple, and so forth for the others.

As another example, suppose we want to find all perfect numbers up to a given value. A perfect number is one where the sum of all its divisors (including 1 but excluding the number itself) equals the number itself. The smallest perfect number is 6, sincd 1+2+3=6. The next is 28. For this, we need an auxiliary function that gives a list of all divisors of a number. This is similar to the function we wrote above for testing if a number is prime:

```(defn divisors [n]
(let [divs (range 1 (inc (quot n 2)))]
(filter #(zero? (rem n %)) divs)))
```

We first form the list divs which contains all numbers from 1 up to n/2 (remember that quot does integer division, throwing away the remainder). We then use the same filter as in prime? above to find all numbers that divide n with no remainder.

Now we can find perfect numbers:

```(defn perfect-less-than [n]
(for [z (range 2 n)
:when (= (reduce + (divisors z)) z)]
z))
```

We test each value of z between 2 and n-1, subjecting it to a :when condition. In this condition, we first find a list of the divisors of z using the divisors function we just defined. Then we use Clojure’s reduce macro. reduce takes a binary function (a function that takes two arguments; the addition function +, here) as its first argument. It then applies this function to the first two elements of its second argument, which is a list. It takes the result of that operation and applies the function to it and the third argument of the list, and so on. Thus in this case, it adds up all the divisors of z. Finally, the :when condition tests if that sum is equal to the original number z. If so, then z is a perfect number.

Although this code does work, it’s not a very efficient way of finding perfect numbers. The first four perfect numbers are 6, 28, 496 and 8128, and the program will find them fairly quickly. The next known perfect number is 33550336, but the given code is far too inefficient to find this in any reasonable time.

for also has two other modifiers that can be applied to each binding. The first is :let, which works in much the same way as the regular let statement. It can be used to define symbols for later use within the for. For example, suppose we wanted to find all pairs of squares whose sum was prime:

```(defn squares-for-primes [n]
(for [x (range 2 (inc n))
:let [xsquared (* x x)]
y (range (inc x) (inc n))
:let [ysquared (* y y)]
:when (prime? (+ xsquared ysquared))]
(list xsquared ysquared)))
```

After the x binding, we’ve used :let to define the symbol xsquared; similarly after the y binding we define ysquared. Also after the y binding, we use a :when to do the check on whether the sum of squares is prime. As a sample of the output:

```=> (squares-for-primes 8)
((4 9) (4 25) (4 49) (9 64) (16 25) (25 36) (25 64) (49 64))
```

The final modifier allowed in for is :while. This means that execution should continue as long as the given condition is true. The difference between :when and :while is that if a :when condition is false, the current value of the variable within a given iteration is skipped and the next value of the variable within the same iteration is processed. If a :while condition is false, the iteration within which it occurred is terminated, with no further values being considered.

As another contrived example, suppose we are given a number x and we want to find pairs of numbers (x,x+1), (x, x+3), (x, x+5)… where the sum of each pair is always prime. (Note that pairs such as (x, x+2) never sum to a prime, since x+x+2=2x+2, which is always divisible by 2.) That is, we want to start with the pair (x, x+1) and then increase the second number of the pair by 2 successively until we hit a pair that doesn’t sum to a prime. (I did say this was contrived.) We can do that like this:

```(defn consec-primes [n]
(for [x (range 1 (inc n))
y (range (inc x) (inc n) 2)
:while (prime? (+ x y))]
(list x y)))
```

The first variable x ranges from 1 to n, and the second starts at x+1 and ranges up to n, but in steps of 2 (if range has 3 arguments, the third is the step size). The iteration over y will continue until the :while condition fails, so for the first value of y where x+y is not prime, iteration over y will stop, and the next value of x will be selected. As an example:

```=> (consec-primes 8)
((1 2) (1 4) (1 6) (2 3) (2 5) (3 4) (5 6) (5 8) (6 7))
```

We see that 1+2, 1+4 and 1+6 are all prime, but 1+8 is not, so it’s excluded from the result.