# Three Ways of Looking at FizzBuzz in J

May 30, 2018 by Seán Stickle

With apologies to Wallace Stevens' Thirteen Ways of Looking at a Blackbird.

## 1. The wycdd Way

``````  fb =: ('FizzBuzz';'Fizz';'Buzz';":){::0 i.15 3 5|]
``````

### Create the Lookup List

Create a list of boxed items that contain all the possible return values:

• “Fizzbuzz” when divided by both 3 and 5
• “Fizz” when divided by 3
• “Buzz” when divided by 5
• The input value when divided by none of the above

Use `;` (link) to build the list of boxed items. To include the input value in the list of boxed items, use `":` (default format) to convert the number to a string:

``````  fb =: 'FizzBuzz' ; 'Fizz' ; 'Buzz' ; ":
input =: 10
fb input

+--------+----+----+--+
|FizzBuzz|Fizz|Buzz|10|
+--------+----+----+--+
``````

### Get the Residues

Take the input number and find out if it’s divisible by 3, 5, or 15. To do this, use `|` (residue), which returns the remainder when dividing by a given number:

``````  n =: 9
15 3 5 | n

9 0 4

n =: 10
15 3 5 | n

10 1 0

n =: 30
15 3 5 | n

0 0 0
``````

For `3` and `5`, there’s only a single `0` returned. For `15`, since all three numbers divide evenly, there are three `0`s returned. If we find the index of the first `0`, we’ll know which number was the greatest divisor with no residue.

### Get the Index

Use `i.` (index of) to find the index of the first `0`. Normally, `i.` operates like `x i. y`, returning the index of the first occurrence of `y` in `x`.

``````  n =: 9

]residues =: 15 3 5 | n

9 0 4

residues i. 0

1
``````

We can also use `~` (passive) to reverse the order, so that it operates like `y. i. x`, allowing us to be more concise:

``````  n =: 9

]residues =: 15 3 5 | n

9 0 4

0 i.~ residues

1

0 i.~ 15 3 5 | n

1
``````

Important note. If the value we’re looking for in the list doesn’t appear, `i.` returns an index that exceeds the size of the list we’re examining. For instance, try finding the index of the first occurrence of either `0` or `19` in the list `5 6 7`:

``````  0 i.~ 5 6 7

3

19 i.~ 5 6 7

3
``````

In a list with only 3 items, index 3 does not exist. This will be useful in the next step.

### Use the Index to Fetch From the Lookup List

We now have a lookup list:

``````  fb =: 'FizzBuzz' ; 'Fizz' ; 'Buzz' ; ":
n =: 10
fb n

+--------+----+----+--+
|FizzBuzz|Fizz|Buzz|10|
+--------+----+----+--+
``````

And an index based on the residues of dividing by 15, 3, and 5:

``````  n =: 10
0 i.~ 15 3 5 | n

2
``````

Use the index to fetch the appropriate value from the lookup list. To do this, use `{::` (fetch):

``````  n =: 3
NB. First occurence of `0` would be at index `1`
(0 i.~ 15 3 5 | input) {:: 'FizzBuzz' ; 'Fizz' ; 'Buzz' ; ": n

Fizz

n =: 5
NB. First occurence of `0` would be at index `2`
(0 i.~ 15 3 5 | input) {:: 'FizzBuzz' ; 'Fizz' ; 'Buzz' ; ": n

Buzz

n =: 15
NB. First occurence of `0` would be at index `0`
(0 i.~ 15 3 5 | input) {:: 'FizzBuzz' ; 'Fizz' ; 'Buzz' ; ": n

FizzBuzz

n =: 7
NB. No residues of `0`, so i. returns `3`
(0 i.~ 15 3 5 | input) {:: 'FizzBuzz' ; 'Fizz' ; 'Buzz' ; ": n

7
``````

### Simplify with a Fork

In J, there is a pattern called a fork, which looks like this:

``````  f g h y
``````

Where `f` is a verb, `g` is a verb, `h` is a verb, and `y` is a noun. Note: For those new to J, read “verb” as function and “noun” as “variable”.

Forks are evaluated like this:

`````` (f y) g (h y)
``````

The canonical example in J is calculating the mean of a set of numbers:

`````` (+/ % #) y
``````

Which is evaluated as:

``````  (+/ y) % (# y)
``````

Which is: the sum of y divided by the count of y.

In our example, we have this code:

``````  (0 i.~ 15 3 5 | n) {:: 'FizzBuzz' ; 'Fizz' ; 'Buzz' ; ": n
``````

Using a fork, we can extract the variable and rewrite this as:

``````  fb =: (0 i.~ 15 3 5 | ]) {:: 'FizzBuzz' ; 'Fizz' ; 'Buzz' ; ":
``````

Notice that we’ve introduced a new verb: `]` (right). We extracted the variable `n`, and `|` (residue) expects two arguments (one on either side), so we had to put in `]` as a placeholder for whatever value we pass to `fb`. There’s more nuance to this that I’ll explain in another post.

### Reverse the Order

We could stop here, as the new verb works great:

``````  fb 1

1

fb 3

Fizz

fb 5

Buzz

fb 15

FizzBuzz
``````

To get to wycdd’s original version, we just need to use `~` (passive) again to reverse the order that `{::` is applied:

``````  fb =: ('FizzBuzz' ; 'Fizz' ; 'Buzz' ; ":) {::~ 0 i.~ 15 3 5 | ]
``````

### Run the Code

Our new verb `fb` only runs on single integers. If we want to apply it to the numbers `1` to `100`, we’ll need to apply it to a whole list. To do that, use `"0`, which tells J to apply the verb to individual atoms of a list. And we’ll use `i.` (integers) to generate a list from `0` to `99` (and add `1` to get a list of `1` to `100`):

``````  fb"0 (1+i.100)

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
...
``````

## 2. Rosetta Code Solution 0

From Solution 0 on Rosetta Code’s FizzBuzz page:

``````  > }. (<'FizzBuzz') (I.0=15|n)} (<'Buzz') (I.0=5|n)} (<'Fizz') (I.0=3|n)} ":&.> n=: i.101
``````

Create a list from `0` to `100` using `i.` (integers):

``````  ]n =: i.101

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88...
``````

### Box It Up

Turn the numeric list into a boxed list. To do this, use `<` (box). By default, `<` will act on the whole list:

``````  < n =: i.101

+-----------------------+
|0 1 2 3 4 5 6 7 8 9 ...|
+-----------------------+
``````

So we’ll use `"` (rank) to apply `<` to each atom (rank `0`) of the list:

``````  <"0 n =: i.101

+-+-+-+-+-+-+-+-+-+-+---+
|0|1|2|3|4|5|6|7|8|9|...|
+-+-+-+-+-+-+-+-+-+-+---+
``````

### Find Numbers Divisible by 3

Find the indexes of all the elements of `n` that are evenly divisible by `3`.

To do this, use `|` (residue) to return the remainders of each number when divided by `3`.

``````  3 | n

0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1
``````

Then, check whether each residues are equal to `0` using `=` (equal):

``````  0 = 3 | n

1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0
``````

Finally, find the index of every `1` in that boolean list:

``````  I. 0 = 3 | n

0 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99
``````

### Amend the Boxed List

With the indexes of all the values that are evenly divisible by `3`, we can update the values the corresponding boxes in our boxed list.

To do this, use `}` (amend). This takes three arguments: `x m } y`, where `y` is the list to update, `m` is an array of cell indexes to update, and `x` is the new value to use in those cells:

``````  y =: <"0 n =: i.101
m =: I. 0 = 3 | n
x =: <'Fizz'
x m } y

+----+-+-+----+-+-+----+-+-+----+---+
|Fizz|1|2|Fizz|4|5|Fizz|7|8|Fizz|...|
+----+-+-+----+-+-+----+-+-+----+---+
``````

Notice that, since we’re updating a boxed list, the value `Fizz` has to be boxed (`<`) as well.

We’ll put this all in one line like this:

``````  (<'Fizz') (I. 0 = 3 | n) } <"0 n =: i.101

+----+-+-+----+-+-+----+-+-+----+---+
|Fizz|1|2|Fizz|4|5|Fizz|7|8|Fizz|...|
+----+-+-+----+-+-+----+-+-+----+---+
``````

### Repeat for 5 and 15

We can do the same “check and amend” process for both `5` and `15`:

``````  (<'Buzz') (I. 0 = 5 | n) } <"0 n =: i.101

+----+-+-+-+-+----+-+-+-+-+----+--+--+---+
|Buzz|1|2|3|4|Buzz|6|7|8|9|Buzz|11|12|...|
+----+-+-+-+-+----+-+-+-+-+----+--+--+---+

(<'FizzBuzz') (I. 0 = 15 | n) } <"0 n =: i.101

+--------+-+-+-+-+-+-+-+-+-+--+--+--+--+--+--------+--+--+---+
|FizzBuzz|1|2|3|4|5|6|7|8|9|10|11|12|13|14|FizzBuzz|16|17|...|
+--------+-+-+-+-+-+-+-+-+-+--+--+--+--+--+--------+--+--+---+
``````

### Combine the Amendments

J evaluates from right to left, the output of one phrase becoming the input of the next. A simple arithmetic example:

``````  6 + 5 * 4 + 3

41
``````

Which evaluates as:

``````  6 + (5 * (4 + 3))

41
``````

In the same way, we can chain our “check and amends” so that the output of one is the input of the next:

``````  (<'FizzBuzz') (I. 0 = 15 | n) } (<'Buzz') (I. 0 = 5 | n) } (<'Fizz') (I. 0 = 3 | n) } <"0 n =: i.101

+--------+-+-+----+-+----+----+-+-+----+----+--+----+--+--+--------+---+
|FizzBuzz|1|2|Fizz|4|Buzz|Fizz|7|8|Fizz|Buzz|11|Fizz|13|14|FizzBuzz|...|
+--------+-+-+----+-+----+----+-+-+----+----+--+----+--+--+--------+---+
``````

Since we want the results for `1` to `100`, we don’t want the first cell in the boxed list. To remove this, use `}.` (behead):

``````}. (<'FizzBuzz') (I. 0 = 15 | n) } (<'Buzz') (I. 0 = 5 | n) } (<'Fizz') (I. 0 = 3 | n) } <"0 n =: i.101

+-+-+----+-+----+----+-+-+----+----+--+----+--+--+--------+---+
|1|2|Fizz|4|Buzz|Fizz|7|8|Fizz|Buzz|11|Fizz|13|14|FizzBuzz|...|
+-+-+----+-+----+----+-+-+----+----+--+----+--+--+--------+---+
``````

### Unboxing Day

Now we’ll unbox everything so that we have a simple list. To do this, use `>` (open):

``````> }. (<'FizzBuzz') (I. 0 = 15 | n) } (<'Buzz') (I. 0 = 5 | n) } (<'Fizz') (I. 0 = 3 | n) } <"0 n =: i.101

|domain error
|       >}.(<'FizzBuzz')(I.0=15|n)}(<'Buzz')(I.0=5|n)}(<'Fizz')(I.0=3|n)}<"0 n=:i.101
``````

Uh oh. This problem is caused because the contents of the boxed list are a combination of `literals` (characters) and `integers`. We can’t create a simple list that contains both.

We’ll need to convert all the numbers to characters.

### Convert to Characters

The easiest place to do that is when we boxed them up in the first place.

``````  <"0 n =: i.101
``````

We’ll do this:

``````  ":&.> n =: i.101
``````

This uses `&.` (under), which takes three arguments: `u &. v y`, where `u` is a verb, `v` is a verb, and `y` is a variable.

For `u`, we’ll use `":` (default format), which converts numbers to characters. For `v`, we’ll use `>` (open).

The order of operation is a little complicated:

1. Executes `v` on `y` cell-by-cell
2. For each cell, `u` is applied to the result of `v`
3. Then `v^:_1` (i.e. the obverse of v) is applied to the result of `u` — giving the result for that cell.

So, for us, this means:

1. Execute `>` (open) on each cell of `y` (`i.101`). These are already unboxed, so this doesn’t do anything.
2. Execute `":` to the result, which converts the numbers to characters.
3. Execute `>^:1`, that is, the inverse of `>` (open), which is the same as `<` (box).
``````  ":&.> n =: i.101

+-+-+-+-+-+-+-+-+-+-+---+
|0|1|2|3|4|5|6|7|8|9|...|
+-+-+-+-+-+-+-+-+-+-+---+
``````

This looks the same as our original, but the values inside those boxes are different.

Here’s the original and the updated boxed lists:

``````  original =: <"0 n =: i.101
updated  =: ":&.> n =: i.101
``````

If we use `{` (from) to take the first element of each boxed list, then use `>` (open) to unbox it, we can then use `datatype` to identify the contents:

``````  > 1 { original

1

datatype > 1 { original

integer

> 1 { updated

1

datatype > 1 { original

literal
``````

### Unboxing Day, Take 2

Updating the code to ensure the contents of the boxed list are all converted to `literals`, we can now try to unbox the results again:

``````  > }. (<'FizzBuzz') (I. 0 = 15 | n) } (<'Buzz') (I. 0 = 5 | n) } (<'Fizz') (I. 0 = 3 | n) } ":&.> n =: i.101

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
...
``````

## 3. Rosetta Code Solution 1

From Solution 1 on Rosetta Code’s FizzBuzz page:

``````  Fizz=: 'Fizz' #~ 0 = 3&|
Buzz=: 'Buzz' #~ 0 = 5&|
FizzBuzz=: ": [^:('' -: ]) Fizz,Buzz
``````

### Fizz for 3

For a number, see if it’s evenly divisible by `3`. We can do this in the same way we’ve done previously, using `|` (residue) and then comparing the result to `0` using `=` (equal):

``````  n =: 9
0 = 3 | n

1
``````

If the result is `1`, we’ll return `Fizz`; if the result is `0`, we’ll return nothing.

We’ll do this by using `#` (copy), which takes two arguments: `x # y`, where `y` is the thing you want copied, and `x` is the number of copies you want. For example, we can create 10 copies of `1`:

``````  10 # 1

1 1 1 1 1 1 1 1 1 1
``````

In our case, we’ll make either `0` or `1` copies of `Fizz`, depending on whether the residue is equal to `0` or not:

``````  n =: 9
(0 = 3 | n) # 'Fizz'

Fizz

n =: 10
(0 = 3 | n) # 'Fizz'
``````

To make this read a little easier, use `~` (passive) with `#` (copy) to flip the order or the arguments:

``````  n =: 9
'Fizz' #~ 0 = 3 | n

Fizz
``````

We can extract the variable and turn this into a standalone verb:

``````  Fizz =: 'Fizz' #~ 0 = 3&|
``````

Notice that to extract the variable, we used `&` (bond) to join an argument (`3`) to the primitive verb `|` (residue). This is how J implements currying, allowing us to pend the full evaluation of the verb until we receive the second argument.

If we don’t bond `3` to `|`, we’d get a syntax error when trying to define this verb:

``````  Fizz =: 'Fizz' #~ 0 = 3 |

|syntax error
|   Fizz=:    'Fizz'#~0=3|
``````

### Buzz for 5

We’ll do the same thing for `5`:

``````  Buzz =: 'Buzz' #~ 0 = 5&|
``````

Easy!

### Forking Fizz and Buzz

Let’s apply both `Fizz` and `Buzz` to a given input. We’ll use `,` (append) to create a list from the results of the two verbs:

``````  n =: 3
(Fizz n) , (Buzz n)

Fizz

n =: 5
(Fizz n) , (Buzz n)

Buzz

n =: 15
(Fizz n) , (Buzz n)

FizzBuzz

n =: 17
(Fizz n) , (Buzz n)
``````

Remember the fork pattern from above?

``````  f g h y
``````

Which evaluates to:

`````` (f y) g (h y)
``````

We can use the fork pattern to simplify our code. Instead of:

``````  (Fizz n) , (Buzz n)
``````

We can use:

``````  (Fizz , Buzz) n
``````

### Is It Empty?

Executing `(Fizz , Buzz)` on the list of `1` to `100` gives us:

``````  (Fizz , Buzz) "0 (1+i.100)

Fizz

Buzz
Fizz

Fizz
Buzz

Fizz

FizzBuzz

Fizz
...
``````

We’re returning the right results for numbers divisible by `3`, `5`, and `15`. We still need to return the input number when not divisible by `3`, `5`, and `15`.

To do this, test to see if the value returned is blank. Use `-:` (match), which takes two arguments, `x -: y`, returning `1` if `x` and `y` match and returning `0` otherwise:

``````  n =: 10
'' -: (Fizz , Buzz) n

0

n =: 7
'' -: (Fizz , Buzz) n

1
``````

We can use this `1` or `0` to decide whether to return the input number or the result of `(Fizz , Buzz)`.

To simplify the code, we ca turn this into a standalone verb by extracting the `(Fizz , Buzz) n`:

``````  is_empty =: '' -: ]
is_empty (Fizz , Buzz) 10

0

is_empty (Fizz , Buzz) 7

1
``````

Note that `-:` (match) expects two arguments, so we’re using `]` (right) to stand in for what we’ll pass as input.

### Fix the Power

We’ll do this by using `^:` (fixed power). This verb takes three arguments, `u ^: n y`, where `u` is applied `n` times to `y`. It’s crucial to know that applying `u` zero times to `y` just returns the original value `y`.

For example, using `*:` (square):

``````  square =: *:
square 5

25

(square^:1) 5

25

(square^:0) 5

5
``````

We can combine this use of fixed power with another `[` (left), a verb that takes two arguments, `x [ y` and always returns the left argument.

``````  1 [ 2

1
``````

Repeated applications of `[` (left) do the same thing:

``````  1 [ [ 2

1
``````

And repeated applications is what `^:` (fixed power) does:

``````  1 [^:(1) 2

1

1 [^:(2) 2

1
``````

But, using the crucial insight from above that raising a verb to the fixed power of `0` just returns the original input:

``````  1 [^:(0) 2

2
``````

This gives us a switch to select the left or the right input, depending on whether we raise `[` (left) to `0` or `1`:

``````  1 [^:(1) 2

1

1 [^:(0) 2

2
``````

This, along with the test we wrote for whether `(Fizz , Buzz)` returns a blank, allows us to write this:

``````  n [ ^:('' -: ]) (Fizz , Buzz) n
``````

If the result of `(Fizz , Buzz)` is blank, then `('' -: ])` returns `1`, which raises `[` to the `1` power, which returns what’s on the left, which is `n`, the input.

If the result of `(Fizz , Buzz)` is not blank (i.e., Fizz, Buzz, or FizzBuzz), then `('' -: ])` returns `0`, which raises `[` to the `0` power, which returns the original input, which is the output of `(Fizz , Buzz)`.

### Hook, Line, Sinker

Notice that our code:

``````  n =: 10
n [ ^:('' -: ]) (Fizz , Buzz) n

Buzz
``````

Can be rewritten as:

``````  f =: [ ^:('' -: ])
g =: Fizz , Buzz
y =: n

y f g y

Buzz
``````

In J, the `y f g y` pattern is known as a `hook`, and it can be written more simply as:

``````  (f g) y

Buzz
``````

In combinatory logic, this is known as the S combinator.

Rewriting the entire sentence using the `hook` structure, we get:

``````  n =: 10
([ ^:('' -: ]) Fizz , Buzz) n

Buzz
``````

We can define this as a standalone verb:

``````  fb =: [ ^:('' -: ]) Fizz , Buzz
fb 3

Fizz

fb 5

Buzz

fb 15

FizzBuzz

fb 17

17
``````

### Apply to the List

Now apply `fb` to the list `1` to `100`, using `"0` (rank) to apply the verb to individual atoms of the list:

``````  fb"0 (1+i.100)

|domain error
|       fb"0(1+i.100)
``````

Oops! This is the same error that we got back in the second way to look at FizzBuzz. We’re mixing `literals` and `integers`, which raises a `domain error`. To fix that, we need to convert all the results to `literals`.

Do that by applying `":` (default format) to the results of our verb, which will convert the `integers` to `literals`:

`````` fb =: ": [ ^:('' -: ]) Fizz , Buzz
``````

Now we can try again:

``````  fb"0 (1+i.100)

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
...
``````

Perfect.

### Coda

It’s interesting to observe that adding the `":` (default format) to the verb:

`````` fb =: ": [ ^:('' -: ]) Fizz , Buzz
``````

Converted it from a hook into a fork:

``````  f =: ":
g =: [ ^:('' -: ])
h =: Fizz , Buzz

(f g h) 15

FizzBuzz

(f g h) 17

17
``````

Which is evaluated as:

``````  (f 15) g (h 15)

FizzBuzz

(f 17) g (h 17)

17
``````

EOF

# Let's Write Quicksort in J

May 28, 2018 by Seán Stickle

This is quicksort in J:

``````  qs =: ((\$:@(<#[), (=#[), \$:@(>#[)) {.) ^: (1<#)
``````

Quicksort is a sorting algorithm. You give it a list of items, it sorts them. Quickly.

If you want to know the detailed version of how it works, consult an algorithms text. Here is the basic version, which I’m lifting from Wikipedia:

1. Pick an element, called a pivot, from the array.
2. Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

## Create an Unsorted Input Array

For testing purposes, we’ll create an unsorted array of 10 elements, each one a random integer from 0 to 99. To do this, we’ll use `?` (roll) and pass it a list of 10 `100`s.

``````  unsorted =: ? 10 # 100

44 35 49 67 95 56 50 35 70 83
``````

## Pick a Pivot

Take `unsorted` and use `{.` (head) to take the first element. That’ll be our pivot:

``````  pivot =: {. unsorted

44
``````

## Find All the Values Greater Than Pivot

Use `>` (larger than) to compare each element of `unsorted` with the pivot. Those that are larger return true (`1`); those that are smaller return false (`0`).

``````  unsorted > pivot

0 0 1 1 1 1 1 0 1 1
``````

Use `#` (copy) to pull a copy of the corresponding elements from `unsorted` where `>` returned true.

``````  NB. unsorted list       -> 44 35 49 67 95 56 50 35 70 83
NB. larger than pivot   ->  0  0  1  1  1  1  1  0  1  1
NB. return these values ->       49 67 95 56 50    70 83

(unsorted > pivot) # unsorted

49 67 95 56 50 70 83
``````

## Bring in the Forks

To make this more concise, we’ll take advantage of a concept in J called a `fork`. A fork is a sequence of three verbs in a row (call them `f`, `g`, and `h`) that operate on an input (call it `y`):

``````  (f g h) y
``````

In J, this is evaluated as:

``````  (f y) g (h y)
``````

This is equivalent to operations on functions in mathematics, such as:

``````  (f + h)(x) = f(x) + h(x)
(f - h)(x) = f(x) - h(x)
(f * h)(x) = f(x) * h(x)
``````

With forks in J, we generalize from the above (`+`, `-`, and `*`) to any operation in the second position.

As some J verbs (`dyadic` verbs) can take 2 arguments, there is a corresponding version of forks for dyadic verbs:

``````  x (f g h) y
``````

This is evaluated as:

``````  (x f y) g (x h y)
``````

Which is equivalent to operations on functions like:

``````  (f + h)(x, y) = f(x,y) + h(x,y)
(f - h)(x, y) = f(x,y) - h(x,y)
(f * h)(x, y) = f(x,y) * h(x,y)
``````

## Greater Than Pivot, Redux

So, using forks, this:

``````  (unsorted > pivot) # unsorted
``````

Can be rewritten as:

``````  unsorted (>#[) pivot
``````

Which will be evaluated as:

``````  (unsorted > pivot) # (unsorted [ pivot)
``````

We’ve introduced a new verb here, `[` (left), which simply returns the value of the argument on the left, regardless of the argument on the right. So this simplifies to:

``````  (unsorted > pivot) # unsorted
``````

Which is what we started with.

So call the new verb `gtp` (greater than pivot):

``````  ]gtp =: unsorted (>#[) pivot

49 67 95 56 50 70 83
``````

## Find All Values Less Than Pivot

Following our logic from `gtp`, we can define `ltp` (less than pivot), this time using `<` (less than):

``````  ]ltp =: unsorted (<#[) pivot

35 35
``````

## Find All Values Equal to Pivot

This time using `=` (equal), we define `etp` (equal to pivot):

``````  ]etp =: unsorted (=#[) pivot

44
``````

## Combine and Simplify

We can organize the results of each of these phrases using `,` (append) to create a new list from the original lists:

``````  ltp , etp , gtp

35 35 44 49 67 95 56 50 70 83
``````

This is equivalent to:

``````  (unsorted (<#[) pivot) , (unsorted (=#[) pivot) , (unsorted (>#[) pivot)
``````

There’s a lot of duplication here. We can simplify this quite a bit.

We have 5 verbs in a row:

``````  ltp , etp , gtp
``````

Remember forks? We can redefine the right three verbs as a fork:

``````  (unsorted (=#[) pivot) , (unsorted (>#[) pivot)

44 49 67 95 56 50 70 83

unsorted ( (=#[) , (>#[) ) pivot

44 49 67 95 56 50 70 83
``````

This leaves us with:

``````  (unsorted (<#[) pivot) , (unsorted ( (=#[) , (>#[) ) pivot)
``````

Which is another string of three verbs. So we can redefine this as a fork:

``````  (unsorted (<#[) pivot) , (unsorted ( (=#[) , (>#[) ) pivot)

35 35 44 49 67 95 56 50 70 83

unsorted ( (<#[) , (=#[) , (>#[) ) pivot

35 35 44 49 67 95 56 50 70 83
``````

Remember back to how `pivot` was defined:

``````  pivot =: {. unsorted
``````

So we can rewrite our fork as:

``````  unsorted ( (<#[) , (=#[) , (>#[) ) {. unsorted

35 35 44 49 67 95 56 50 70 83
``````

Notice the structure of the sentence now, treating the entire verb train as a single verb

``````  f =: ( (<#[) , (=#[) , (>#[) )
g =: {.
y =: unsorted

y f g y

35 35 44 49 67 95 56 50 70 83
``````

In J, the `y f g y` pattern is known as a `hook`, and it can be written more simply as:

``````  (f g) y

35 35 44 49 67 95 56 50 70 83
``````

In combinatory logic, this is known as the S combinator.

Rewriting the entire sentence using the `hook` structure, we get:

``````  (( (<#[) , (=#[) , (>#[) ) {.) unsorted

35 35 44 49 67 95 56 50 70 83
``````

## Recurse

Now that we’ve simplified the structure, let’s continue with the sorting.

We’ve made a single pass, creating three sub-arrays — numbers less that the pivot, numbers equal to the pivot, and numbers greater than the pivot. However, the numbers in each of those groups are not themselves sorted.

Now we’ll proceed to step 3 of the algorithm:

Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

To do this, we’ll recursively invoke our quicksort code on the sub-arrays by combining the `ltp` and `gtp` phrases with the name of the sentence itself. We do that using `@` (atop), which produces a single verb from two verbs.

If we represent that as `f@g`, then `f` will be applied to the results of `g` applied to a input value. In this case, we want to apply `qs` to the result of the `ltp` and `gtp` phrases. We don’t need to recurse on the `etp` phrase, because there’s nothing to sort there — everything in that sub-array is equal to the pivot.

``````  qs =: (( qs@(<#[) , (=#[) , qs@(>#[) ) {.)
qs unsorted

|stack error: qs
|       qs unsorted
``````

That’s not good. We recursed so many times that we exceeded the recursion limit. We need a way of identifying when to stop recursing.

J will stop recursing when the code returns a constant function.

In our case, we’ll use `^:` (fixed power), which will apply the entire sentence to the input a number of times. It’s critical to know that any verb raised to the 0 power (`^:0`) will always return the input — a constant function. Raising a verb to the 0 power is just another way of saying that we're going to apply the verb to the input 0 times (not at all).

For instance, we can define a verb that will double the input:

``````  double =: 2&*
double 2

4
``````

We can apply that verb to the input a number of times. For example, let’s apply it 5 times:

``````  (double^:5) 2

64
``````

But if we apply it zero times, we get the input as the output:

``````  (double^:0) 2

2
``````

Using this insight, we’ll use `^:` with our quicksort definition.

First, we’ll check whether the length of the input is greater than 1. If the comparison is true (`1`), then there are 2 or more items to sort, so apply the function 1 time and return the calculated output. If the comparison is false (`0`), then there is only 0 or 1 elements to sort (which is to say, there is no need to sort), so apply the function 0 times, and return the input as the output.

``````  qs =: (( qs@(<#[) , (=#[) , qs@(>#[) ) {.) ^: (1<#)
qs unsorted

35 35 44 49 50 56 67 70 83 95
``````

This time, we didn’t exhaust the recursion limit, and we got the fully sorted list back. Success!

## Anonymous Recursion

Our recursion code explicitly refers to the name of the function. What happens if we change the name of the function?

``````  qs_new =: (( qs@(<#[) , (=#[) , qs@(>#[) ) {.) ^: (1<#)
qs_new unsorted

|value error: qs
|       qs_new unsorted
``````

To avoid this, we can use `\$:` (self-reference) to refer to the recursive verb without specifying the name:

``````  qs =: (( \$:@(<#[) , (=#[) , \$:@(>#[) ) {.) ^: (1<#)
qs unsorted

35 35 44 49 50 56 67 70 83 95
``````

We have now constructed the quicksort code from the beginning of the article. QEF.

## Taciturn

If you’ve been reading closely, you’ll notice that we stopped putting the name of the unsorted array on the same line as the verb definition, and we didn’t replace it with a variable to hold the input:

``````  qs =: (( \$:@(<#[) , (=#[) , \$:@(>#[) ) {.) ^: (1<#)
``````

J allows verbs to be defined tacitly:

In a tacit definition the arguments are not named and do not appear explicitly in the definition. The arguments are referred to implicitly by the syntactic requirements of the definition.

J makes extensive use of tacit programming, allowing the structure of the code to emerge more clearly. That’s a story for another time.

EOF

# Let's Write Life in J

May 28, 2018 by Seán Stickle

TL;DR — one J program for Conway’s Game of Life is:

``````  ((3&=) +. (y&*.)@(4&=)) +/ (> , {;~ 1 0 _1) |. y
``````

## Create the Input Array

First, we need an input for the Game of Life program to run on.

Create a 5x5 table with an embedded glider:

``````  ]R =: 5 5 \$ 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0

0 0 0 0 0
0 0 1 0 0
0 0 0 1 0
0 1 1 1 0
0 0 0 0 0
``````

## Rotate the Array

For each cell, get a count of how many neighbor cells are alive (`1`) or dead (`0`).

Let’s take a simplified example. Take a 1x5 table

``````  0 1 0 1 0
``````

If we want to count how many neighbors of the each cell are alive, we can generate and then add two new tables: the original table rotated to the right and the original table rotated to the left. Note: we’re assuming that this table wraps around.

``````  rotated_right =: 0 0 1 0 1
rotated_left  =: 1 0 1 0 0
rotated_right + rotated_left

1 0 2 0 1
``````

The result is the number of alive cells horizontally adjacent to each cell.

For our 2-dimensional table, we can do the same thing — except we’ll generate new tables by rotating left, right, up, down, and diagonally up and down. Then we’ll add up all the tables to get the sum of adjacent cells that are alive.

To do this, we’ll use the `|.` (rotate) verb. We’ll pass two numbers, the first rotating vertically and the second rotating horizontally. Positive numbers rotate up/left, negative numbers rotate down/right.

``````  1 1 |. R

0 1 0 0 0
0 0 1 0 0
1 1 1 0 0
0 0 0 0 0
0 0 0 0 0

_1 _1 |. R

0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 0 0 1
0 0 1 1 1

1 _1 |. R

0 0 0 1 0
0 0 0 0 1
0 0 1 1 1
0 0 0 0 0
0 0 0 0 0
``````

Let’s do more than one rotation at a time. We’ll do this by passing an array of multiple rotation values.

Use the `,:` (laminate) verb to build a table from two lists. Then we can use `,` (append) to add additional lists.

To generate the same three tables as above, we’d create a table with 3 lists.

``````  1 1 , _1 _1 ,: 1 _1

1  1
_1 _1
1 _1

(1 1 , _1 _1 ,: 1 _1) |. R

0 1 0 0 0
0 0 1 0 0
1 1 1 0 0
0 0 0 0 0
0 0 0 0 0

0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 0 0 1
0 0 1 1 1

0 0 0 1 0
0 0 0 0 1
0 0 1 1 1
0 0 0 0 0
0 0 0 0 0
``````

We can apply all nine rotations this way, explicitly listing each rotation combination:

``````  (0 1 , 1 0 , 1 _1 , 0 1 , 0 0 , 0 _1 , _1 1 , _1 0 ,: _1 _1) |. R

0 1 0 0 0
0 0 1 0 0
1 1 1 0 0
0 0 0 0 0
0 0 0 0 0

0 0 1 0 0
0 0 0 1 0
0 1 1 1 0
0 0 0 0 0
0 0 0 0 0

0 0 0 1 0
0 0 0 0 1
0 0 1 1 1
0 0 0 0 0
0 0 0 0 0

0 0 0 0 0
0 1 0 0 0
0 0 1 0 0
1 1 1 0 0
0 0 0 0 0

0 0 0 0 0
0 0 1 0 0
0 0 0 1 0
0 1 1 1 0
0 0 0 0 0

0 0 0 0 0
0 0 0 1 0
0 0 0 0 1
0 0 1 1 1
0 0 0 0 0

0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 1 0 0
1 1 1 0 0

0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 1 0
0 1 1 1 0

0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 0 0 1
0 0 1 1 1
``````

It’d be cleaner if we could generate all the rotation combinations. We can do this using `{` (catalogue), which allows us to create a Cartesian product of two lists.

Catalogue takes a `boxed list`, a particular kind of datatype in J. We can create a boxed list by using `;` (link) to create a list of boxed items.

``````  1 0 _1 ; 1 0 _1

+--------+--------+
| 1 0 _1 | 1 0 _1 |
+--------+--------+
``````

Then we pass this boxed list to `{` to get the Cartesian product:

``````  { 1 0 _1 ; 1 0 _1

+-------+-------+-------+
|  1  1 |  1  0 |  1 _1 |
+-------+-------+-------+
|  0  1 |  0  0 |  0 _1 |
+-------+-------+-------+
| _1  1 | _1  0 | _1 _1 |
+-------+-------+-------+
``````

From here, we convert the 2-dimensional boxed list into a 1-dimensional boxed list by using `,` (ravel):

``````  , { 1 0 _1 ; 1 0 _1

+-----+-----+------+-----+-----+------+------+------+-------+
| 1 1 | 1 0 | 1 _1 | 0 1 | 0 0 | 0 _1 | _1 1 | _1 0 | _1 _1 |
+-----+-----+------+-----+-----+------+------+------+-------+
``````

Finally, we unbox the entire thing, which converts it into the 2-dimensional array we wanted:

``````  > , { 1 0 _1 ; 1 0 _1

1  1
1  0
1 _1
0  1
0  0
0 _1
_1  1
_1  0
_1 _1
``````

We can reduce this further. As we’ve used it, `;` takes two arguments, the left `1 0 _1` and the right `1 0 _1`. In J, we represent this as `x ; y`. In our case, as both arguments are identical, we can use `~` (reflex) in combination with `;` — this use of `~` takes a single argument and copies it on both sides of the verb, so that `;~ y` is the same as `y ; y`:

``````  ;~ 1 0 _1

+--------+--------+
| 1 0 _1 | 1 0 _1 |
+--------+--------+
``````

So we can say:

``````  > , {;~ 1 0 _1

1  1
1  0
1 _1
0  1
0  0
0 _1
_1  1
_1  0
_1 _1
``````

And now we can use this to build the rotated tables:

``````  (> , {;~ 1 0 _1) |. R

0 1 0 0 0
0 0 1 0 0
1 1 1 0 0
0 0 0 0 0
0 0 0 0 0

0 0 1 0 0
0 0 0 1 0
0 1 1 1 0
0 0 0 0 0
0 0 0 0 0

0 0 0 1 0
0 0 0 0 1
0 0 1 1 1
0 0 0 0 0
0 0 0 0 0

0 0 0 0 0
0 1 0 0 0
0 0 1 0 0
1 1 1 0 0
0 0 0 0 0

0 0 0 0 0
0 0 1 0 0
0 0 0 1 0
0 1 1 1 0
0 0 0 0 0

0 0 0 0 0
0 0 0 1 0
0 0 0 0 1
0 0 1 1 1
0 0 0 0 0

0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 1 0 0
1 1 1 0 0

0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 1 0
0 1 1 1 0

0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 0 0 1
0 0 1 1 1
``````

Now, let’s reduce all these tables into a single table by adding up all the corresponding elements. To do this, we’ll use `+/` (sum)

``````  +/ (> , {;~ 1 0 _1) |. R

0 1 1 1 0
0 1 2 2 1
1 3 5 4 2
1 2 4 3 2
1 2 3 2 1
``````

## Living Cells in the Next Generation

The rules of Conway’s Game of Life stipulate that a cell is alive in the next generation if:

1. The cell is alive in the current generation and has `2` or `3` living neighbors
2. The cell is dead in the current generation and has `3` living neighbors

### Cells with Value of 3

Any cell with `3` will be alive in the next generation, regardless of whether it is alive in the current generation — either it is currently alive (`1`) and has `2` living neighbors, or it is currently dead (`0`) and has `3` living neighbors.

We can find all cells with a `3` by using `=` (equal):

``````  3 = +/ (> , {;~ 1 0 _1) |. R

0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 1 0
0 0 1 0 0
``````

We can turn the phrase `3 =` into a standalone verb by currying it. To curry a verb in J, we use `&` (bond):

``````  (3&=) +/ (> , {;~ 1 0 _1) |. R

0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 1 0
0 0 1 0 0
``````

We’ll use this bonded verb soon.

### Cells with Value of 4

A cell with `4` will be alive in the next generation if it is alive (`1`) in the current generation and has `3` living neighbors. On the other hand, a cell with `4` that is dead (`0`) in the current generation and has `4` living neighbors will be dead in the next generation.

Let’s first find the cells that have `4`

``````  4 = +/ (> , {;~ 1 0 _1) |. R

0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 0 0 0
``````

Let’s bond `4 =`:

``````  (4&=) +/ (> , {;~ 1 0 _1) |. R

0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 0 0 0
``````

Then we’ll use `*.` (AND) to select only those cells with `4` that are alive (`1`) in the current generation:

``````  R *. (4&=) +/ (> , {;~ 1 0 _1) |. R

0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 0 0 0
``````

Let’s bond `R *.`:

``````  (R&*.) (4&=) +/ (> , {;~ 1 0 _1) |. R

0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 0 0 0
``````

Let’s compose the two bonded verbs — `R&*.` and `4&=` into a single verb. In J, we do this with `@` (atop):

``````  (R&*.)@(4&=) +/ (> , {;~ 1 0 _1) |. R

0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 0 0 0
``````

### Get the Cells with 3s OR 4s

The reason for the bonding and composing is that we can now combine both tests and apply them together using `+.` (OR):

``````  ((3&=) +. (R&*.)@(4&=)) +/ (> , {;~ 1 0 _1) |. R
``````

This returns the logical OR of the two tables we generated that checked for cells with `3` and the cells with `4` (that are currently alive).

The phrase `((3&=) +. (R&*.)@(4&=))` contains three verbs in a row `(3&=)`, `+.`, and `(R&*.)@(4&=)`. In J, this is called a train and it has some rather deep and elegant interpretations. But that’s a story for a different time.

## Convert to Verb

Finally, we’ll convert to a standalone verb, with `y` representing the input array:

``````  life =: verb define
((3&=) +. (y&*.)@(4&=)) +/ (> , {;~ 1 0 _1) |. y
)
``````

## Results

Now we can apply our verb to the original input:

``````  ]R =: 5 5 \$ 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0

0 0 0 0 0
0 0 1 0 0
0 0 0 1 0
0 1 1 1 0
0 0 0 0 0

life R

0 0 0 0 0
0 0 0 0 0
0 1 0 1 0
0 0 1 1 0
0 0 1 0 0
``````

We can apply `life` to the output of `life` as well:

``````  life life R

0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 1 0 1 0
0 0 1 1 0
``````

Using `^:` (fixed power), we can apply the same function to its own output as many times as we like. To get the same output as `life life R`, we can raise `life` to the second power.

``````  life^:2 R

0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 1 0 1 0
0 0 1 1 0
``````

If we give `^:` an array, it will run once for each element and output the complete set of results. For `i.2` (the array `0 1`), it produces 2 generations (the original generation for `0` and the next generation for `1`:

``````  life^:(i.2) R

0 0 0 0 0
0 0 1 0 0
0 0 0 1 0
0 1 1 1 0
0 0 0 0 0

0 0 0 0 0
0 0 0 0 0
0 1 0 1 0
0 0 1 1 0
0 0 1 0 0
``````

Finally, if we run `life` 20 times, we can see that the glider will return to it’s original position in our 5x5 table:

``````  life^:(i.20) R

0 0 0 0 0
0 0 1 0 0
0 0 0 1 0
0 1 1 1 0
0 0 0 0 0

0 0 0 0 0
0 0 0 0 0
0 1 0 1 0
0 0 1 1 0
0 0 1 0 0

0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 1 0 1 0
0 0 1 1 0

0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 1 1
0 0 1 1 0

0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 0 0 1
0 0 1 1 1

0 0 0 1 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 1
0 0 0 1 1

0 0 0 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1
0 0 1 0 1

0 0 0 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
1 0 0 0 1

1 0 0 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1
1 0 0 0 0

1 0 0 0 1
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
1 0 0 1 0

1 0 0 1 0
1 0 0 0 1
0 0 0 0 0
0 0 0 0 0
1 0 0 0 0

1 1 0 0 0
1 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1

0 1 0 0 0
1 1 0 0 1
0 0 0 0 0
0 0 0 0 0
1 0 0 0 0

0 1 0 0 1
1 1 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0

0 1 0 0 0
0 1 0 0 1
1 1 0 0 0
0 0 0 0 0
0 0 0 0 0

1 0 0 0 0
0 1 1 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 0 0

0 1 0 0 0
0 0 1 0 0
1 1 1 0 0
0 0 0 0 0
0 0 0 0 0

0 0 0 0 0
1 0 1 0 0
0 1 1 0 0
0 1 0 0 0
0 0 0 0 0

0 0 0 0 0
0 0 1 0 0
1 0 1 0 0
0 1 1 0 0
0 0 0 0 0

0 0 0 0 0
0 1 0 0 0
0 0 1 1 0
0 1 1 0 0
0 0 0 0 0
``````

## Coda

Thanks to Jordan Scales, who provided the code for this exploration. And thanks to Words and Buttons for their APL Game of Life post that provided the inspiration for this J version.

EOF