Elegant Programming
Vector 12:2, page 123
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 123
Part 1 &. dfh¶
J defines inverses for many functions, and provides various ways of making use of them. A recent addition to the set of inverses in J2.06, namely the inverse to n&#., enables the elegant title expression, and prompted this note. We will look first at the title expression, and then examine how it works.
First define:
Then:
Thus, hex is an adverb which returns a verb that works in hexadecimal.
Under¶
The definition of hex uses the conjunction &. (under). Given verbs u and v where the inverse \(\mathtt{v}^{-1}\) is defined, then u&.v is equivalent to \(\mathtt{v}^{-1}\) u v.
Here are some examples:
inverse of natural log is the exponential:
inverse of reciprocal is itself:
inverse of open is box:
n=. 'winston';(i.3 4);10 20
# &.> n
┌─┬─┬─┐
│7│3│2│
└─┴─┴─┘
$ &.> n
┌─┬───┬─┐
│7│3 4│2│
└─┴───┴─┘
each=. &.>
|. each n
┌────────┬──────────┬─────┐
│notsniw │8 9 10 11 │20 10│
│ │4 5 6 7 │ │
│ │0 1 2 3 │ │
└────────┴──────────┴─────┘
inverse of the binary representation is the base-2 value:
bitwise=. &.#:
5 +. bitwise 6 NB. bitwise OR
7
5 *. bitwise 6 NB. bitwise AND
4
5 ~: bitwise 6 NB. bitwise XOR
3
inverse of transpose is itself:
+/\ i.3 4 NB. accumulate along columns
0 1 2 3
4 6 8 10
12 15 18 21
+/\ &.|: i.3 4 NB. accumulate along rows
0 1 3 6
4 9 15 22
8 17 27 38
Inverse¶
You can access the inverse directly using ^:_1 (power of minus 1). For example, define:
inverse of add 2 is subtract 2:
inverse of sum scan is first differences:
inverse of product scan is rate of increase:
inverse of p: determines number of smaller primes:
Obverse¶
You can define inverses for use with the conjunctions &. and ^: directly, using the conjunction :. (obverse). The result of u :. v is a verb that is equivalent to u with an assigned obverse v.
In general, the term obverse is used instead of inverse, since the defined obverse need not be a true inverse, indeed it may be an unrelated verb.
For example:
%: (*:2) + (*:5) NB. square root of 2^2 + 5^2
5.38516
2 + &. *: 5 NB. same
5.38516
2 +&.(*: :. (^&1r2)) 5 NB. same (inverse of *: is square root)
5.38516
2 +&.(*: :. (^&1r3)) 5 NB. using cube root as obverse
3.07232
Hex¶
Now let’s take a closer look at the definition of hex:
The inverse of '0123456789ABCDEF'&i. is:
while the inverse of 16&#. is:
with as many 16’s as required.
Also, the inverse of f @ g is \(\mathtt{g}^{-1}\) @ \(\mathtt{f}^{-1}\), hence the inverse of dfh can be calculated.
For any verb f:
Part 2 #~ 1: = #@q:¶
This elegant expression uses the verb q: introduced in J2.06, and provides an interesting exercise for the newcomer to J. The expression contains a hook, a fork, an adverb, a conjunction, and a constant function. It is fair to say that once you understand this expression, then you also understand the essence of functional programming in J.
First let’s use the definition, as follows:
p=. #~ 1: = #@q:
p 2+i.30
2 3 5 7 11 13 17 19 23 29 31
p 123456+i.50
123457 123479 123491 123493 123499 123503
Thus, p selects the primes in a list of positive integers. How does it work?
The definition of p can be read from left to right as: select where 1 is the number of prime factors.
Let’s build up this definition step by step.
q: returns the prime factors of its argument, for example:
The verb #@q: returns the count of the number of prime factors. Here, the conjunction @ (atop) creates a new verb that applies # to the result of q:.
We now want to generate a boolean where a 1 indicates a prime, i.e. where the count of the number of prime factors is 1. This is achieved by the following fork:
The 1: needs some explanation. A fork is a sequence of three verbs, f g h where:
Note that the three elements of a fork are verbs. In the definition of p1, the leftmost verb is 1:, which is a verb that returns the value 1, given any argument. Here, J makes clear the difference between a number, and a verb that returns that number. This distinction is not made in standard mathematical notation, which can be confusing.
We now use the boolean to select the primes. The selection verb is #, which takes a boolean left argument:
In this case, however, we want to use # with the boolean as a right argument. To do so, we create a new verb with the adverb ~ (passive), that swaps its arguments:
(You can read # as select, and #~ as select where.)
Finally, we define p as the hook p2 p1, giving us the original definition of p. A hook is a sequence of two verbs f g, where:
Box Display¶
Box display helps clarify the structure of functional expressions, and should be used by default as a learning aid. You graduate from the school of functional programming when you find that you no longer need box display to read functional expressions! For example:
p
┌─────┬───────────────┐
│┌─┬─┐│┌──┬─┬────────┐│
││#│~│││1:│=│┌─┬─┬──┐││
│└─┴─┘││ │ ││#│@│q:│││
│ ││ │ │└─┴─┴──┘││
│ │└──┴─┴────────┘│
└─────┴───────────────┘
In box display, elements are grouped into twos and threes, as follows:
- 2 elements:
- if the right element is an adverb, then the two elements represent the verb formed by applying the adverb to the argument on its left, otherwise, the two elements are a train (in the case of 2 verbs, a hook).
- 3 elements:
- if the center element is a conjunction, then the three elements represent the verb formed by applying the conjunction to its two arguments, otherwise, the three elements are a train (in the case of 3 verbs, a fork).
With this in mind, we can see from the above box display that p is a hook. The left element is the result of applying the adverb ~ to the verb #. The right element is a fork, whose rightmost element is the result of applying the conjunction @ to the verbs # and q:.
Here are a couple more examples to illustrate:
t0=. +/ @ (1: = (+. i.))
t0
┌─────┬─┬──────────────┐
│┌─┬─┐│@│┌──┬─┬───────┐│
││+│/││ ││1:│=│┌──┬──┐││
│└─┴─┘│ ││ │ ││+.│i.│││
│ │ ││ │ │└──┴──┘││
│ │ │└──┴─┴───────┘│
└─────┴─┴──────────────┘
Here t0 is the result of applying the conjunction @, with a left argument of sum (+/), and a right argument of a fork, whose rightmost element is the hook (+. i.).
The expression +. i. computes the GCD (+.) of an integer and all the integers below it. For example,
Thus, t1 defined below takes an integer argument and computes which integers below it are relatively prime to it (i.e. the GCD is 1):
Therefore t0, which is defined as +/ @ t1, is Euler’s totient function, i.e. the number of integers below a number that are relatively prime to it.
A more efficient version is:
Can you read its box display?