Leaping not looping

Today two things. We’ll solve a simple problem in all-at-once array style. And we’ll use an operator to do it. The problem is determining whether a year is a leap year. Simples. But first the operator.

Operator has a special meaning in APL. An operator modifies one function to produce another. (APL here follows the usage of Heaviside, an early user of vectors in mathematics.) For example, the reduction operator / modifies the addition function + so that +/ is the sum function:

      +/1 2 3 4
10

(You can experiment with the expressions in this post at TryAPL.org)

Similarly, ×/ is product and ⌊/ and ⌈/ are respectively minimum and maximum.

    ×/1 2 3 4
24
    ⌊/1 2 3 4
1
    ⌈/1 2 3 4
4

The J language neatly catches the relationship between functions and operators: it calls them verbs and adverbs.

Here is the outer product operator .∘ at work, modifying + and × into functions that return addition and multiplication tables:

      10 20 ∘.+ 1 2 3 4
11 12 13 14
21 22 23 24
      10 20 ∘.× 1 2 3 4
10 20 30 40
20 40 60 80

Our simple problem is to flag which in a list of years are leap years. You probably know the rule: a year is a leap year if it is divisible by 4 — unless it is also divisible by 100, in which case it is not — unless it is also divisible by 400, in which case it is.

Neither 1901 nor 2001 are leap years, because they are not divisible by 4. 1904 and 2004 are both leap years, because they are divisible by 4 and not by 100. 1900 was not a leap year, because it was divisible by 100 but not 400. And 2000 was a leap year because it was divisible by 400.

We can express this quite conventionally in a control structure:

     ∇ Z←isLeap1 years;i
[1]    Z←(≢years)⍴0
[2]    :For i :In ⍳≢years
[3]        :If Z[i]←0=4|years[i]
[4]        :AndIf 0=100|years[i]
[5]            Z[i]←0=400|years[i]
[6]        :EndIf
[7]    :EndFor
     ∇

We’re using the modulus function | to test the remainder after dividing the year by, successively, 400, 100 and 4.

      isLeap1 1900 1901 1904 2000 2001 2004
0 0 1 1 0 1

That succeeds, but uses no array thinking. Array thinking goes more like this. Divide all the years by all the divisors to see the remainders:

      400 100 4∘.| 1900 1901 1904 2000 2001 2004
300 301 304 0 1 4
  0   1   4 0 1 4
  0   1   0 0 1 0

We’re interested only in the sign of the remainders:

      ×400 100 4∘.| 1900 1901 1904 2000 2001 2004
1 1 1 0 1 1
0 1 1 0 1 1
0 1 0 0 1 0

A column for each year, each column three flags. For leap years all the flags must be down (divisible by 400) or only the bottom one (divisible by 4 only). But we can treat each column of flags as a binary number and decode it ⊥ as a decimal number:

      2⊥×400 100 4∘.| 1900 1901 1904 2000 2001 2004
4 7 6 0 7 6

In this scheme the leap years show up as either 0 or 6. The membership function ∊ will flag them:

      (2⊥×400 100 4∘.| 1900 1901 1904 2000 2001 2004) ∊ 0 6
0 0 1 1 0 1

To make a function from this expression, embrace it and replace the data with ⍵ (‘wha’ever’) placeholder:

      {(2⊥×400 100 4∘.| ⍵) ∊ 0 6}

Or, for a finishing touch, we can use the commute operator ⍨ to switch the arguments of the membership function and so lose the annoying parentheses:

      isLeap2←{0 6 ∊⍨2⊥×400 100 4∘.| ⍵}
      isLeap2 1900 1901 1904 2000 2001 2004
0 0 1 1 0 1

Now here’s an array-ish thing. You probably spotted the simple pattern in the list of years: the two centuries and the first and fourth years after them. More neatly expressed as an outer product of +:

      1900 2000 ∘.+ 0 1 4
1900 1901 1904
2000 2001 2004

Pleasingly, isLeap2 returns its result in the same shape as its argument:

      isLeap2 1900 2000 ∘.+ 0 1 4
0 0 1
1 0 1

We’ve touched here on three operators: reduce, commute, and outer product. Operators give us great expressive power in describing ways to apply functions across or through arrays. Moreover, you can write your own. For a more elaborate example, see Industrial FP: A case study.

The array thinking characteristically gave us some over-computing: isLeap2 divides every year in the array by three numbers. isLeap1 makes fewer comparisons. On the other hand, its greater code volume has to be parsed by the interpreter, and under the outer product operator, the interpreter has more scope for optimisation or even parallelisation.

Thanks to Tommy Luff for help testing the sample problem.