By: Stefan Kruger
Recently, I was looking for a Dyalog problem to pit my wits against, and I asked in the APL Orchard if Adám could make one up:
A CMC, if you’re unfamiliar with the APL Orchard, is a Chat Mini Challenge – typically an informal code golf challenge to produce the shortest possible bit of code that solves the set problem. Code golf practitioners usually delve into the dustiest corners of a language and, if practiced diligently, this can lead to a deep mastery over time, even if some dirty hacks techniques employed may be frowned upon in production code.
Anyway. Adám responded with the following:
The Mysterious Case of 0 0⍴0
Hmm. What even is that thing‽ It’s only 5 characters already – not much scope to shrink that, surely? Let’s have a look at it with full boxing:
⎕IO←0
]Box on -style=max
┌→────────────────┐
│Was ON -style=max│
└─────────────────┘
0 0⍴0
┌⊖┐
⌽0│
└~┘
In the boxed output, the ⌽ tells us that the leading axis has length 0, the ⊖ means that the trailing axis has length 0, and the ~ means that the array is non-nested.
This is a simple numeric array of two dimensions, each of length 0 – think of it as a spreadsheet or table before you’ve put any rows or columns of data in it.
I found this problem difficult to get started with, so I searched for the expression on APL Cart, and discovered that:
]Box off
Was ON
]APLCart 0 0⍴0 ⍝ Dyalog 18.1 has APLCart built in! Fancy.
X,Y,Z:any M,N:num I,J:int A,B:Bool C,D:char f,g,h:fn ax:axis s:scal v:vec m:mat
───────────────────────────────────────────────────────────────────────────────
⍬⊤⍬ zero-by-zero numeric matrix
───────────────────────────────────────────────────────────────────────────────
Showing 1 of 1 matches
]Box on
┌→──────┐
│Was OFF│
└───────┘
Surely not? Let’s try that suggestion:
(0 0⍴0)≡⍬⊤⍬
1
Well, it clearly works, but why? Let’s see if we can figure that one out.
In the basic case for encode, X⊤Y, if X and Y are vectors, the result will have one column for each element in Y and one row for each element in X. Using the example from the language bar:
2 2 2 2 ⊤ 5 7 12 ⍝ Convert decimal to binary
┌→────┐
↓0 0 1│
│1 1 1│
│0 1 0│
│1 1 0│
└~────┘
we have a shape of 4 3, as the length of the vector to the left (2 2 2 2) is 4 and the length of the vector to the right (5 7 12) is 3.
Returning to ⍬⊤⍬, given the above, we can deduce that the result should have a rank of 2 with a shape of 0 0 which, of course, is what we wanted to achieve:
⍴⍬⊤⍬ ⍝ Shape 0 0
┌→──┐
│0 0│
└~──┘
Disappointingly, I had to cheat by looking up the answer. However, are there any more length-3 solutions? Apparently, ⍬⊤⍬ is “reasonably well known”. I decided to write a simple brute-force search function to look for any other solutions.
This works as follows:
- Create all possible length-3 combinations of APL glyphs
- Evaluate each in turn, skipping those that error
- Save those that evaluate to
0 0⍴0
Here’s what I ended up with:
∇ r←Bruter target;glyphs;combo;eval
glyphs ← '0⍬+-×÷*⍟⌹○|⌈⌊⊥⊤⊣⊢=≠≤<>≥≡≢∨∧⍲⍱↑↓⊂⊃⊆⌷⍋⍒⍳⍸∊⍷∪∩~/\⌿⍀,⍪⍴⌽⊖⍉¨⍨⍣.∘⍤⍥@⌸⌺⍎⍕¯'
r ← ⍬
:For combo :In ,∘.,⍣2⍨glyphs
:Trap 0
eval ← ⍎combo
:Else
:Continue
:EndTrap
:If eval≡target
r ,← ⊂combo
:EndIf
:EndFor
∇
I decided to leave out a few glyphs that I guessed would be unlikely to feature (←→⎕⍠⍞⍝⋄), and I only added the number 0. Let’s see what that generates:
7 5⍴Bruter 0 0⍴0 ⍝ 7×5 layout added for clarity after the fact
┌→──────────────────────────────┐
↓ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ │
│ │⍬⊤⍬│ │+⌸⍬│ │-⌸⍬│ │×⌸⍬│ │÷⌸⍬│ │
│ └───┘ └───┘ └───┘ └───┘ └───┘ │
│ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ │
│ │*⌸⍬│ │⍟⌸⍬│ │○⌸⍬│ │|⌸⍬│ │⌈⌸⍬│ │
│ └───┘ └───┘ └───┘ └───┘ └───┘ │
│ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ │
│ │⌊⌸⍬│ │⊤⍨⍬│ │⊤⌸⍬│ │⊢⌸⍬│ │=⌸⍬│ │
│ └───┘ └───┘ └───┘ └───┘ └───┘ │
│ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ │
│ │≠⌸⍬│ │≤⌸⍬│ │<⌸⍬│ │>⌸⍬│ │≥⌸⍬│ │
│ └───┘ └───┘ └───┘ └───┘ └───┘ │
│ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ │
│ │∨⌸⍬│ │∧⌸⍬│ │⍲⌸⍬│ │⍱⌸⍬│ │↑⍸0│ │
│ └───┘ └───┘ └───┘ └───┘ └───┘ │
│ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ │
│ │↑⌸⍬│ │↓⌸⍬│ │⍷⌸⍬│ │∩⌸⍬│ │/⌸⍬│ │
│ └───┘ └───┘ └───┘ └───┘ └───┘ │
│ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ │
│ │⌿⌸⍬│ │⍴⌸⍬│ │⌽⌸⍬│ │⊖⌸⍬│ │⍉⌸⍬│ │
│ └───┘ └───┘ └───┘ └───┘ └───┘ │
└∊──────────────────────────────┘
Wow! There are 35 of them (for ⎕IO←0)!
There are clearly patterns here – we can see our friend ⍬⊤⍬ right at the beginning, and also its equivalent ⊤⍨⍬. We can also see ↑⍸0 which, in retrospect, perhaps I should have thought of in the first place.
The remaining 32 solutions all feature key. The majority of those have a scalar function operand; we can treat this whole group as equivalent. Let’s tackle that group first, with the operand + as the example:
+⌸⍬
┌⊖┐
⌽0│
└~┘
Let’s recap what key does. The operand dyadic function is called with each unique element of the argument in turn as its left argument, and a vector of indices of occurrences as its right. Key then returns a rank 2 array of the results. For example:
{⍺ ⍵}⌸'Mississippi'
┌→─────────────┐
↓ ┌→┐ │
│ M │1│ │
│ - └~┘ │
│ ┌→───────┐ │
│ i │2 5 8 11│ │
│ - └~───────┘ │
│ ┌→──────┐ │
│ s │3 4 6 7│ │
│ - └~──────┘ │
│ ┌→───┐ │
│ p │9 10│ │
│ - └~───┘ │
└∊─────────────┘
With an argument of the empty vector ⍬, in the operand function, ⍺ will always be 0 – the prototype element of our empty numeric vector:
{⎕←⍺}⌸⍬
0
What about ⍵? Well, it must be an empty numeric vector (no found indices):
{⎕←⍵}⌸⍬
┌⊖┐
│0│
└~┘
So, with a scalar function like + as the operand, we end up with 0+⍬. Key returns an array where each major cell is the result of the function applied to the unique element and its indices, which in this case is an array with major cells of the structure ⍬. How many such major cells? 0. So the result is 0⌿1 0⍴⍬, which is, of course, 0 0⍴0.
So for 0 f ⍬ for any scalar dyadic function f, the above holds. For example:
0>⍬
┌⊖┐
│0│
└~┘
>⌸⍬
┌⊖┐
⌽0│
└~┘
Then we have a lot of non-scalar operands, like ⊖/⍷↑↓. All we need to understand is why they produce ⍬ when applied as 0 f ⍬, as key will call them. Some of these are pretty obvious, like find, ⍷:
0⍷⍬ ⍝ Find all locations of 0 in the empty vector
┌⊖┐
│0│
└~┘
or take and drop, ↑↓:
0↑⍬ ⍝ Take no elements from the beginning of the empty vector
┌⊖┐
│0│
└~┘
0↓⍬ ⍝ Drop no elements from the end of the empty vector
┌⊖┐
│0│
└~┘
However, ⍉ gives us a dyadic transpose – and, perhaps unexpectedly, this one is ⎕IO-dependent:
0⍉⍬
┌⊖┐
│0│
└~┘
At first glance, this made no sense to me. The reason this works is that transposing a vector is an identity operation:
⍉'Transposing a vector returns the vector'
┌→──────────────────────────────────────┐
│Transposing a vector returns the vector│
└───────────────────────────────────────┘
A vector has a single axis, so “reordering the axes” doesn’t do anything. The same holds true for the dyadic form, assuming the left argument is ⎕IO:
0⍉'Same for the dyadic form. Sometimes.'
┌→───────────────────────────────────┐
│Same for the dyadic form. Sometimes.│
└────────────────────────────────────┘
This is the reason why this only works for ⎕IO←0: Key always provides 0 for the left argument. For ⎕IO←1 we will get a DOMAIN ERROR:
⎕IO←1
0⍉'Same for the dyadic form. Sometimes.'
DOMAIN ERROR
0⍉'Same for the dyadic form. Sometimes.'
∧
A few others stand out. Replicate (and its sibling replicate-first), for example:
/⌸⍬
┌⊖┐
⌽0│
└~┘
will end up as:
0/⍬ ⍝ zero empty vectors
┌⊖┐
│0│
└~┘
in the left operand – zero empty vectors is still the empty vector. Reshape is similar:
0⍴⍬ ⍝ zero empty vectors
┌⊖┐
│0│
└~┘
Encode tries to express ⍬ in the 0 radix; also an empty vector:
0⊤⍬
┌⊖┐
│0│
└~┘
My favourite, though, is probably ↑⍸0, and, as I said earlier, I’m a bit disappointed I didn’t find that before resorting to brute force and ignorance. Where (⍸) returns a vector of indices with 1 for its Boolean array right argument. If we call it with a right argument of 0, we’ll get an empty vector of empty numeric vectors. This is because the one (and only) valid index into a scalar is the empty vector, and none of them (!) are non-zero.
⍸0
┌⊖────┐
│ ┌⊖┐ │
│ │0│ │
│ └~┘ │
└∊────┘
Trading depth for rank, we get the shape we want:
↑⍸0
┌⊖┐
⌽0│
└~┘
What About 0⍴⊂⍬?
The expression ⍸0 above is the only length-2 way to produce an empty vector of empty numeric vectors:
(⍸0)≡0⍴⊂⍬
1
However, there are several interesting length-3 solutions. Deploying the Bruter again:
8 7⍴res←Bruter 0⍴⊂⍬
┌→──────────────────────────────────────────┐
↓ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ │
│ │0⊂0│ │0⊂⍬│ │0⊆⍬│ │⍬⊂0│ │⍬⊂⍬│ │⍬⊆⍬│ │+⍸0│ │
│ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ │
│ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ │
│ │-⍸0│ │×⍸0│ │÷⍸0│ │*⍸0│ │⍟⍸0│ │○⍸0│ │|⍸0│ │
│ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ │
│ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ │
│ │⌈⍸0│ │⌊⍸0│ │⊣⍸0│ │⊢⍸0│ │⊂⍨0│ │⊂⍨⍬│ │⊆⍸0│ │
│ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ │
│ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ ┌→──┐ │
│ │⊆⍨⍬│ │⌷⍸0│ │⍳¨⍬│ │⍸00│ │⍸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│ │⍴¨⍬│ │⌽⍸0│ │⊖⍸0│ │⍉⍸0│ │
│ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ │
└∊──────────────────────────────────────────┘
Most are ⍸0 combined with an additional primitive that has no effect, or selfie-mirrors, so let’s restrict ourselves to the interesting subset:
4 2⍴res/⍨~'⍸⍨'∘(∨/∊)¨res ⍝ Skip variants of ⍸0 and selfies
┌→────────────┐
↓ ┌→──┐ ┌→──┐ │
│ │0⊂0│ │0⊂⍬│ │
│ └───┘ └───┘ │
│ ┌→──┐ ┌→──┐ │
│ │0⊆⍬│ │⍬⊂0│ │
│ └───┘ └───┘ │
│ ┌→──┐ ┌→──┐ │
│ │⍬⊂⍬│ │⍬⊆⍬│ │
│ └───┘ └───┘ │
│ ┌→──┐ ┌→──┐ │
│ │⍳¨⍬│ │⍴¨⍬│ │
│ └───┘ └───┘ │
└∊────────────┘
We can see a few patterns again – partition (⊆) or partitioned enclose (⊂), with 0 as left or right argument and ⍬ as left or right argument, plus two variants using each (¨) on ⍬. Let’s look at ⊂ first.
Partitioned enclose groups, or partitions, stretches its right argument as specified by its Boolean vector left argument, with each new partition starting on 1, and returns a nested vector of the resulting partitions:
1 0 0 0 0 1 1 0 0 0 0⊂'Hello World'
┌→────────────────────┐
│ ┌→────┐ ┌→┐ ┌→────┐ │
│ │Hello│ │ │ │World│ │
│ └─────┘ └─┘ └─────┘ │
└∊────────────────────┘
In the first case, 0⊂0, we’re saying that we want 0 partitions of 0 (which gets treated as a 1-element vector), returned as a nested vector – in other words, exactly the “empty vector of empty numeric vectors” that we’re after. In fact, ⊂ with a 0 as its left argument returns an empty vector of empty vectors of the prototype element of the right, which also helps to explain our 0⊂⍬:
0⊂'hello world' ⍝ Empty vector of empty character vectors
┌⊖────┐
│ ┌⊖┐ │
│ │ │ │
│ └─┘ │
└∊────┘
0⊂1 2 3 4 5 ⍝ Empty vector of empty numeric vectors
┌⊖────┐
│ ┌⊖┐ │
│ │0│ │
│ └~┘ │
└∊────┘
0⊂⍬ ⍝ Empty vector of empty numeric vectors
┌⊖────┐
│ ┌⊖┐ │
│ │0│ │
│ └~┘ │
└∊────┘
Swapping the order of that last expression:
⍬⊂0
┌⊖────┐
│ ┌⊖┐ │
│ │0│ │
│ └~┘ │
└∊────┘
is really the same thing: the left side is still a numeric vector with no 1s.
What about ⊆? If we restrict ourselves to a Boolean left argument again, partition is similar to replicate, but instead of just skipping elements of the right side corresponding to 0s in the left side, it encloses groups of elements corresponding to 1s, and skips the rest:
1 1 1 1 1 0 1 1 1 1 1⊆'Hello World'
┌→────────────────┐
│ ┌→────┐ ┌→────┐ │
│ │Hello│ │World│ │
│ └─────┘ └─────┘ │
└∊────────────────┘
Compare with replicate:
1 1 1 1 1 0 1 1 1 1 1/'Hello World'
┌→─────────┐
│HelloWorld│
└──────────┘
As with ⊂, ⊆ returns a vector of vectors and, by the same reasoning, if the left argument contains no 1s, then the inner vector will be an empty vector of the prototype element of the right argument:
0⊆1 2 23 34
┌⊖────┐
│ ┌⊖┐ │
│ │0│ │
│ └~┘ │
└∊────┘
We should understand the remaining ⊆ variant, ⍬⊆⍬, too. You might wonder why there is no 0⊆0, analogous to the 0⊂0 we saw earlier; a fair question. However, it results in an error:
0⊆0 ⍝ RANK ERROR
RANK ERROR
0⊆0 ⍝ RANK ERROR
∧
The reason for this is that ⊆ is IBM’s APL2 primitive, supplied for compatibility reasons. It simply doesn’t treat a scalar right argument as a 1-element vector, unlike ⊂.
What remains are the two variants using the each operator: ⍳¨⍬ and ⍴¨⍬. Each always returns an array of the same shape as its right argument, in which each element is the result of applying the operand to the corresponding element in the argument.
By that reasoning, with an argument of ⍬ we’ll always end up with an empty vector. The prototype element is itself a vector, as both ⍳ and ⍴ returns vectors – and, in our specific case, empty numeric vectors, as given the argument ⍬.
Closing Remark
Many people – certainly including myself – find reasoning about the behaviour of empty arrays in Dyalog APL difficult. Going through exercises such as these can help to make this clearer.
Follow