cburke@jsoftware.com

This elegant expression 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 lets 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 equals the number of prime factors.*

Lets build up this definition step by step.

`q:`

returns the prime factors of its argument, for example:

q: 123456 2 2 2 2 2 2 3 643

The verb
`#@q:`

returns the count of the number of prime factors.
Here, the conjunction
`@`

(atop) creates a new verb that applies
`q:`

to its argument, then `#`

to the result of `q:`

.

p0=: #@q: p0 123456 8

We next 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:

p1=: 1: = p0 p1 2+i.12 1 1 0 1 0 1 0 0 0 1 0 1

The `1:`

needs some explanation. A fork is a sequence of three verbs,
`f g h`

where:

(f g h) x <=> (f x) g (h x)

Note that the three elements of a fork are verbs. In the definition of
`p`

, 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 blurred in standard mathematical notation.

We now use the boolean to select the primes. The selection verb is
`#`

, which
takes a boolean left argument:

1 1 0 1 0 1 # 2 3 4 5 6 7 2 3 5 7

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
`~`

(pass), that swaps its arguments:

p2=: #~ 2 3 4 5 6 7 p2 1 1 0 1 0 1 2 3 5 7

(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:

(f g) x <=> x f g x

p +-----+---------------+ |+-+-+|+--+-+--------+| ||#|~|||1:|=|+-+-+--+|| |+-+-+|| | ||#|@|q:||| | || | |+-+-+--+|| | |+--+-+--------+| +-----+---------------+

In box display, elements are grouped into twos and threes, as follows:

- 2 elements: if the right element is an adverb, and 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 element in the centre 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.
Its 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
`@`

, 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,

(+. i.) 12 12 1 2 3 4 1 6 1 4 3 2 1

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):

t1=: 1: = (+. i.) t1 12 0 1 0 0 0 1 0 1 0 0 0 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.

t0 12 4

A more efficient version is:

t3=: * -.@%@~.&.q: t3 12 4

Can you read its box display?

t3 +-+-----------------------+ |*|+---------------+--+--+| | ||+--------+-+--+|&.|q:|| | |||+--+-+-+|@|~.|| | || | ||||-.|@|%|| | || | || | |||+--+-+-+| | || | || | ||+--------+-+--+| | || | |+---------------+--+--+| +-+-----------------------+