Code Golf: Generating Empty Arrays

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:

  1. Create all possible length-3 combinations of APL glyphs
  2. Evaluate each in turn, skipping those that error
  3. 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.

Towards Improvements to Stencil

Background

The stencil operator was introduced in Dyalog version 16.0 in 2017. Recently we received some feedback (OK, complaints) that (a) stencil does padding which is unwanted sometimes and needs to be removed from the result and (b) stencil is too slow when it is not supported by special code.

First, stencil in cases supported by special code is much faster than when it is not. The special cases are as follows, from Dyalog ’17 Workshop SA3.

   {⍵}      {⊢⍵}      {,⍵}      {⊂⍵}
{+/,⍵}    {∧/,⍵}    {∨/,⍵}    {=/,⍵}    {≠/,⍵}  
    
{  +/,A×⍵}    {  +/⍪A×⍤2⊢⍵}
{C<+/,A×⍵}    {C<+/⍪A×⍤2⊢⍵}
C:  a single number or variable whose value is a single number
A:  a variable whose value is a rank-2 or 3 array
The comparison can be < ≤ ≥ > = ≠
odd window size; movement 1; matrix argument
 

You can test whether a particular case is supported by using a circumlocution to defeat the special case recognizer.

   )copy dfns cmpx

   cmpx '{⍵}⌺3 5⊢y' '{⊢⊢⍵}⌺3 5⊢y' ⊣ y←?100 200⍴0
  {⍵}⌺3 5⊢x   → 4.22E¯4 |      0%                               
  {⊢⊢⍵}⌺3 5⊢x → 5.31E¯2 | +12477% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

   cmpx '{⌽⍵}⌺3 5⊢y' '{⊢⊢⌽⍵}⌺3 5⊢y'
  {⌽⍵}⌺3 5⊢y   → 2.17E¯1 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  {⊢⊢⌽⍵}⌺3 5⊢y → 2.21E¯1 | +1% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

If the timings are the same then there is no special code.

Padding and performance improvements will take a lot of work. For example, for padding (i.e. the treatment of cells at the edge of the universe) multiple options are possible: no padding, padding, wrap from opposite edge, etc. While working on these improvements I hit upon the idea of writing a stencil function which produces the stencil cells. It only works with no padding and only for movements of 1 (which I understand are common cases), but turns out to be an interesting study.

A Stencil Function

⍺ stencell ⍵ produces the stencil cells of size from  , and is equivalent to {⍵}⌺⍺⊢⍵ after the padded cells are removed.

stencell←{
  ⎕io←0                 ⍝ ⎕io delenda est!
  s←(≢⍺)↑⍴⍵
  f←1+s-⍺               ⍝ frame AKA outer shape
  m←⊖×⍀⊖1↓s,1           ⍝ multiplier for each axis
  i←⊃∘.+⌿(m,m)×⍳¨f,⍺    ⍝ indices
  (⊂i) ⌷ ⍵ ⍴⍨ (×⌿(≢⍺)↑⍴⍵),(≢⍺)↓⍴⍵
}

For example, stencell is applied to x with cell shape 3 5 .

   ⊢ x←6 10⍴⍳60                    ⍝ (a)
 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

   c←3 5 stencell x                ⍝ (b)
   ⍴c
4 6 3 5

   c ≡ 1 2 ↓ ¯1 ¯2 ↓ {⍵}⌺3 5 ⊢x    ⍝ (c)
1

   ⊢ e←⊂⍤2 ⊢c                      ⍝ (d)
┌──────────────┬──────────────┬──────────────┬──────────────┬──────────────┬──────────────┐
│ 0  1  2  3  4│ 1  2  3  4  5│ 2  3  4  5  6│ 3  4  5  6  7│ 4  5  6  7  8│ 5  6  7  8  9│
│10 11 12 13 14│11 12 13 14 15│12 13 14 15 16│13 14 15 16 17│14 15 16 17 18│15 16 17 18 19│
│20 21 22 23 24│21 22 23 24 25│22 23 24 25 26│23 24 25 26 27│24 25 26 27 28│25 26 27 28 29│
├──────────────┼──────────────┼──────────────┼──────────────┼──────────────┼──────────────┤
│10 11 12 13 14│11 12 13 14 15│12 13 14 15 16│13 14 15 16 17│14 15 16 17 18│15 16 17 18 19│
│20 21 22 23 24│21 22 23 24 25│22 23 24 25 26│23 24 25 26 27│24 25 26 27 28│25 26 27 28 29│
│30 31 32 33 34│31 32 33 34 35│32 33 34 35 36│33 34 35 36 37│34 35 36 37 38│35 36 37 38 39│
├──────────────┼──────────────┼──────────────┼──────────────┼──────────────┼──────────────┤
│20 21 22 23 24│21 22 23 24 25│22 23 24 25 26│23 24 25 26 27│24 25 26 27 28│25 26 27 28 29│
│30 31 32 33 34│31 32 33 34 35│32 33 34 35 36│33 34 35 36 37│34 35 36 37 38│35 36 37 38 39│
│40 41 42 43 44│41 42 43 44 45│42 43 44 45 46│43 44 45 46 47│44 45 46 47 48│45 46 47 48 49│
├──────────────┼──────────────┼──────────────┼──────────────┼──────────────┼──────────────┤
│30 31 32 33 34│31 32 33 34 35│32 33 34 35 36│33 34 35 36 37│34 35 36 37 38│35 36 37 38 39│
│40 41 42 43 44│41 42 43 44 45│42 43 44 45 46│43 44 45 46 47│44 45 46 47 48│45 46 47 48 49│
│50 51 52 53 54│51 52 53 54 55│52 53 54 55 56│53 54 55 56 57│54 55 56 57 58│55 56 57 58 59│
└──────────────┴──────────────┴──────────────┴──────────────┴──────────────┴──────────────┘

    ∪¨ ,¨ e-⍬⍴e                    ⍝ (e)
┌──┬──┬──┬──┬──┬──┐
│0 │1 │2 │3 │4 │5 │
├──┼──┼──┼──┼──┼──┤
│10│11│12│13│14│15│
├──┼──┼──┼──┼──┼──┤
│20│21│22│23│24│25│
├──┼──┼──┼──┼──┼──┤
│30│31│32│33│34│35│
└──┴──┴──┴──┴──┴──┘
(a)  The matrix x is chosen to make stencil results easier to understand.
(b) stencell is applied to x with cell shape 3 5 .
(c) The result of stencell is the same as that for {⍵}⌺ after cells with padding are dropped.
(d) Enclose the matrices in c (the cells) to make the display more compact and easier to understand.
(e) Subsequent discussion is based on the observation that each cell is some scalar integer added to the first cell.

Indices

The key expression in the computation is

   ⊃∘.+⌿(m,m)×⍳¨f,⍺ 

where

   m:  10 1;  multiplier for each axis
   f:  4 6;  multiplier for each axis
   ⍺:  3 5;  multiplier for each axis
 

We discuss a more verbose but equivalent version of this expression,

   (⊃∘.+⌿m×⍳¨f)∘.+(⊃∘.+⌿m×⍳¨⍺)

and in particular the right half, ⊃∘.+⌿m×⍳¨⍺ , which produces the first cell.

   ⍳⍺               ⍝ ⍳3 5
┌───┬───┬───┬───┬───┐
│0 0│0 1│0 2│0 3│0 4│
├───┼───┼───┼───┼───┤
│1 0│1 1│1 2│1 3│1 4│
├───┼───┼───┼───┼───┤
│2 0│2 1│2 2│2 3│2 4│
└───┴───┴───┴───┴───┘
   (⍴⍵)∘⊥¨⍳⍺        ⍝ 6 10∘⊥¨ ⍳3 5
 0  1  2  3  4
10 11 12 13 14
20 21 22 23 24

Alternatively, this last result obtains by multiplying by m the corresponding indices for each axis, where an element of m is the increment for a unit in an axis. That is, m←⊖×⍀⊖1↓s,1 where s←(≢⍺)↑⍴⍵ is a prefix of the shape of  . The multipliers are with respect to the argument because the indices are required to be with respect to the argument  .

   ⍳¨⍺              ⍝ ⍳¨3 5
┌─────┬─────────┐
│0 1 2│0 1 2 3 4│
└─────┴─────────┘
   m×⍳¨⍺            ⍝ 10 1×⍳¨3 5
┌───────┬─────────┐
│0 10 20│0 1 2 3 4│
└───────┴─────────┘
   ∘.+⌿ m×⍳¨⍺       ⍝ ∘.+⌿ 10 1×⍳¨3 5
┌──────────────┐
│ 0  1  2  3  4│
│10 11 12 13 14│
│20 21 22 23 24│
└──────────────┘
   ((⍴⍵)∘⊥¨⍳⍺) ≡ ⊃∘.+⌿m×⍳¨⍺
1

This alternative computation is more efficient because it avoids creating and working on lots of small nested vectors and because the intermediate results for ∘.+⌿ grows fast from one to the next (i.e., O(⍟n) iterations in the main loop).

The left half, ⊃∘.+⌿m×⍳¨f , is similar, and computes the necessary scalar integers to be added to the result of the right half.

   ⊃ ∘.+⌿ m×⍳¨f     ⍝ ⊃ ∘.+⌿ 10 1×⍳¨4 6
 0  1  2  3  4  5
10 11 12 13 14 15
20 21 22 23 24 25
30 31 32 33 34 35

The shorter expression derives from the more verbose one by some simple algebra.

(⊃∘.+⌿m×⍳¨f)∘.+(⊃∘.+⌿m×⍳¨⍺)    ⍝ verbose version
⊃∘.+⌿(m×⍳¨f),m×⍳¨⍺             ⍝ ∘.+ is associative
⊃∘.+⌿(m,m)×(⍳¨f),⍳¨⍺           ⍝ m× distributes over ,
⊃∘.+⌿(m,m)×⍳¨f,⍺               ⍝ ⍳¨ distributes over ,

I am actually disappointed that the shorter expression was found ☺; it would have been amusing to have a non-contrived and short expression with three uses of ∘.+ .

Cells

Having the indices i in hand, the stencil cells obtain by indexing into an appropriate reshape or ravel of the right argument  . In general, the expression is

   (⊂i) ⌷ ⍵ ⍴⍨ (×/(≢⍺)↑⍴⍵),(≢⍺)↓⍴⍵

specifies the cell shape. If (≢⍺)=≢⍴⍵ , that is, if a length is specified for each axis of  , the expression is equivalent to (⊂i)⌷,⍵ or (,⍵)[i] ; if (≢⍺)<≢⍴⍵ , that is, if there are some trailing unstencilled axes, the expression is equivalent to (,[⍳≢⍺]⍵)[i;…;] (the leading ≢⍺ axes are ravelled) or ↑(,⊂⍤((≢⍴⍵)-≢⍺)⊢⍵)[i] (as if the trailing axes were shielded from indexing). The general expression covers both cases.

Application

stencell makes it possible to workaround current shortcomings in . The alternative approach is to use stencell to get all the stencil cells, all at once, and then work on the cells using  , +.× , and
other efficient primitives.

The following example is from Aaron Hsu. In the original problem the size of x is 512 512 64 .

   K←?64 3 3 64⍴0
   x←?256 256 64⍴0

   t←1 1↓¯1 ¯1↓{+/⍪K×⍤3⊢⍵}⌺3 3⊢x
   ⍴t
256 256 64

   cmpx '1 1↓¯1 ¯1↓{+/⍪K×⍤3⊢⍵}⌺3 3⊢x'
6.76E0 

The computation is slow because the cells are rank-3, not supported by special code. Aaron then devised a significant speed-up using a simpler left operand to create the ravels of the cells (but still no special code):

   t ≡ (1 1↓¯1 ¯1↓{,⍵}⌺3 3⊢x)+.×⍉⍪K
1
   cmpx '(1 1↓¯1 ¯1↓{,⍵}⌺3 3⊢x)+.×⍉⍪K'
1.67E0 

Use of stencell would improve the performance a bit further:

   t ≡ (,⍤3 ⊢3 3 stencell x)+.×⍉⍪K
1
   cmpx '(,⍤3 ⊢3 3 stencell x)+.×⍉⍪K'
1.09E0 

   cmpx '3 3 stencell x'
6.10E¯2

The last timing shows that the stencell computation is 6% (6.10e¯2÷1.09e0) of the total time.

Materializing all the cells does take more space than if the computation is incorporated in the left operand of  , and is practicable only if the workspace sufficiently large.

   )copy dfns wsreq

   wsreq '1 1↓¯1 ¯1↓{+/⍪K×⍤3⊢⍵}⌺3 3⊢x'
110649900
   wsreq '(1 1↓¯1 ¯1↓{,⍵}⌺3 3⊢x)+.×⍉⍪K'
647815900
   wsreq '(,⍤3 ⊢3 3 stencell x)+.×⍉⍪K'
333462260

Performance

stencell is competitive with {⍵}⌺ on matrices, where it is supported by special code written in C, and is faster when there is no special code. The benchmarks are done on a larger argument to reduce the effects of padding/unpadding done in {⍵}⌺ .

   y2←?200 300⍴0
          
   cmpx '3 5 stencell y2' '1 2↓¯1 ¯2↓{⍵}⌺3 5⊢y2' 
  3 5 stencell y      → 1.85E¯3 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕           
  1 2↓¯1 ¯2↓{⍵}⌺3 5⊢y → 2.91E¯3 | +57% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

   cmpx '3 5 stencell y' '{⍵}⌺3 5⊢y' 
  3 5 stencell y → 1.85E¯3 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
* {⍵}⌺3 5⊢y      → 1.04E¯3 | -45% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕             

   y3←?200 300 64⍴0

   cmpx '3 5 stencell y3' '1 2↓¯1 ¯2↓{⍵}⌺3 5⊢y3' 
  3 5 stencell y3      → 8.90E¯2 |    0% ⎕⎕⎕                           
  1 2↓¯1 ¯2↓{⍵}⌺3 5⊢y3 → 7.78E¯1 | +773% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

   cmpx '3 5 stencell y3' '{⍵}⌺3 5⊢y3' 
  3 5 stencell y3 → 9.38E¯2 |    0% ⎕⎕⎕⎕⎕⎕⎕⎕                      
* {⍵}⌺3 5⊢y3      → 3.34E¯1 | +256% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

There is an interesting question of whether the shorter version of the key computation (in the Indices section above) is faster than the more verbose version.

   m←10 1 ⋄ f←4 6 ⋄ a←3 5

   cmpx '⊃∘.+⌿(m,m)×⍳¨f,a' '(⊃∘.+⌿m×⍳¨f)∘.+(⊃∘.+⌿m×⍳¨a)'
  ⊃∘.+⌿(m,m)×⍳¨f,a            → 3.75E¯6 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  (⊃∘.+⌿m×⍳¨f)∘.+(⊃∘.+⌿m×⍳¨a) → 5.20E¯6 | +38% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

In this case, it is faster, and I expect it will be faster for cases which arise in stencil calculations, where the argument size is larger than the cell size. But it is easy to think of arguments where ∘.+⌿ is slower than ∘.+ done with a different grouping:

   cmpx '((⍳0)∘.+⍳100)∘.+⍳200' '(⍳0)∘.+((⍳100)∘.+⍳200)' '⊃∘.+/⍳¨0 100 200'
  ((⍳0)∘.+⍳100)∘.+⍳200   → 7.86E¯7 |     0% ⎕⎕                            
  (⍳0)∘.+((⍳100)∘.+⍳200) → 1.05E¯5 | +1234% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕  
  ⊃∘.+/⍳¨0 100 200       → 1.11E¯5 | +1310% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

This question will be explored further in a later post.

Ascending and Descending

Lexicographic Ordering

Lexicographic ordering is what the APL primitives and provide:

   ⎕io←0     ⍝ ⎕io delenda est
   ⎕rl←7*5   ⍝ to get reproducible random results

   a←?11 3⍴3

   a          a ⌷⍨⊂ ⍋a
2 1 0      0 1 0
0 2 2      0 2 2
1 1 1      1 0 0
1 0 0      1 0 1
1 1 1      1 0 1
1 2 1      1 1 0
1 0 1      1 1 1
1 0 1      1 1 1
1 1 0      1 2 1
0 1 0      1 2 2
1 2 2      2 1 0

First order by column 0, resulting in groups of rows with the same values in column 0. Then, within each group, order by column 1, getting subgroups with the same values in columns 0 and 1. Then, within each subgroup, order by column 2, getting subsubgroups with the same values in columns 0, 1, and 2. In general, for each subsub…subgroup, order by column k, getting groups with identical values in columns ⍳k.

The preceding discourse is descriptive rather than prescriptive—algorithms for can use more efficient and more straightforward approaches. As well, for ease of understanding, the description is for a matrix and speaks of columns and rows. In general, any non-scalar array can be ordered, whence instead of rows, think major cells, instead of column, think item in a major cell. Symbolically and more succinctly, ⍋⍵ ←→ ⍋⍪⍵.

can be used if the orderings in the process are all ascending, or if all descending. The problem to be solved here is where the orderings are a mix of ascending and descending.

Numeric Arrays

Since ⍒⍵ ←→ ⍋-⍵ if is numeric, for such multiply each descending column by ¯1 and each ascending column by 1, then apply . This induces a “control array” having the same shape as a major cell of the argument, with a ¯1 for descending and a 1 for ascending.

   adn←{⍵ ⌷⍨⊂ ⍋ ⍺ ×⍤99 ¯1 ⊢⍵}

For the array a in the previous section:

   a              1 ¯1 1 adn a        ¯1 1 1 adn a
2 1 0          0 2 2               2 1 0  
0 2 2          0 1 0               1 0 0  
1 1 1          1 2 1               1 0 1  
1 0 0          1 2 2               1 0 1  
1 1 1          1 1 0               1 1 0  
1 2 1          1 1 1               1 1 1  
1 0 1          1 1 1               1 1 1  
1 0 1          1 0 0               1 2 1  
1 1 0          1 0 1               1 2 2  
0 1 0          1 0 1               0 1 0  
1 2 2          2 1 0               0 2 2  

In 1 ¯1 1 adn a, column 0 is ascending, and within that, column 1 is descending, and within that, column 2 is ascending. In ¯1 1 1 adn a, column 0 is descending, and within that, column 1 is ascending, and within that, column 2 is ascending.

Ordinals

An array to be sorted can be converted to an order-equivalent integer array by assigning to each item an ordinal (an integer) which has the same ordering relationship as the original item relative to other items in the array:

   sort    ← {(⊂⍋⍵)⌷⍵}
   ordinal ← {⎕ct←0 ⋄ ⍵⍳⍨sort,⍵}

That is, the ordinals obtain as the indices of the original array in the sorted list of the ravelled elements, using exact comparisons. (Exact comparisons are used because sorting necessarily uses exact comparisons.)
For example:

   ⊢ d←¯1 'syzygy' (3 ¯5) 1j2 'chthonic' (¯1)
┌──┬──────┬────┬───┬────────┬──┐
│¯1│syzygy│3 ¯5│1J2│chthonic│¯1│
└──┴──────┴────┴───┴────────┴──┘
   ordinal d
0 5 3 2 4 0

In the example, the data items are ¯1, 'syzygy', 'chthonic', 3 ¯5, 1j2, and ¯1 again. With respect to ordering, these data items are perfectly represented by the ordinals (numbers) 0, 5, 3, 2, 4, and 0, respectively. That is, ⍋d ←→ ⍋ordinal d.

   ⍋ d
0 5 3 2 4 1
   ⍋ ordinal d
0 5 3 2 4 1

As the example illustrates, it is imperative that identical ordinals are assigned to identical items, else the ordering relationships would be changed. For example, if b←0,⍪2 1 and the 0s are assigned different ordinals,

   ⊢ b←0,⍪2 1               
0 2
0 1
   ordinal b                 ⊢ bo←0 3,⍪1 2  ⍝ faux ordinals
0 3                       0 3
0 2                       1 2
   ⍋ ordinal b               ⍋ bo
1 0                       0 1
   ⍋ b
1 0

Computation of ordinals is greatly facilitated by the total array ordering introduced in Dyalog APL version 17.0.

Non-Numeric Arrays

A general solution for the ordering problem obtains by first converting the array to an order-equivalent integer array through the use of ordinals.

   ado ← {⍵ ⌷⍨⊂ ⍋ ⍺ ×⍤99 ¯1 ordinal ⍵}

For example:

   ⎕rl←7*5   ⍝ to get reproducible random results

   x0← ?19⍴4                            
   x1← (⊂?19⍴2) ⌷ 'alpha' 'beta'          
   x2← (⊂?19⍴3) ⌷ 'abc'                   
   x3← (⊂?19⍴3) ⌷ 'able' 'baker' 'charlie'

   x ← x0,x1,x2,⍪x3

   ordinal x
13 49 19 42
10 49 32 68
13 49 63 68
 4 49 63 42
 0 27 19 23
13 49 32 42
 0 49 19 42
10 49 32 68
10 27 32 23
 4 49 32 68
 4 49 32 68
 4 27 32 23
 4 49 32 68
 0 49 63 68
13 49 63 68
 0 49 32 42
13 27 32 23
 4 27 63 42
13 49 19 42

   (⍋x) ≡ ⍋ ordinal x
1

Suppose x is to be sorted ascending in columns 0 and 2 and descending in columns 1 and 3. The control array is 1 ¯1 1 ¯1, and:

   x                       1 ¯1 1 ¯1 ado x
┌─┬─────┬─┬───────┐     ┌─┬─────┬─┬───────┐
│2│beta │b│baker  │     │0│beta │a│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│able   │     │0│beta │b│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│beta │b│able   │     │0│beta │b│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│b│baker  │     │0│beta │c│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│1│beta │b│charlie│     │0│beta │c│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│1│beta │a│baker  │     │0│alpha│c│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │c│charlie│     │1│beta │a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │b│baker  │     │1│beta │b│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │c│able   │     │1│alpha│c│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │a│able   │     │2│beta │a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│baker  │     │2│beta │b│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│baker  │     │3│beta │b│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│1│alpha│c│able   │     │3│beta │b│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│beta │b│charlie│     │3│beta │c│charlie│
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│0│alpha│c│baker  │     │3│alpha│a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│beta │b│able   │     │3│alpha│a│baker  │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│2│beta │a│baker  │     │3│alpha│a│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│beta │c│charlie│     │3│alpha│a│able   │
├─┼─────┼─┼───────┤     ├─┼─────┼─┼───────┤
│3│alpha│a│able   │     │3│alpha│b│baker  │
└─┴─────┴─┴───────┘     └─┴─────┴─┴───────┘

Finally

   (ordinal x) ≡ ordinal ordinal x
1

That is, ordinal is idempotent. Actually, this is kind of obvious, but I never miss an opportunity to use the word “idempotent”.☺

Dyalog ’18 Videos, Week 6

Happy New Year – and Welcome to the 6th week of Dyalog ’18 video releases!

If you enjoy geometry, 2019 starts with a couple of real treats; one which builds up to the use of complex numbers just before the end, and another which starts with them and moves on to Quaternions. Alternatively, if you think vectors and matrices containing imaginary numbers are a bit esoteric, what could be more “down to earth” than taking a look at various ways to efficiently extract data from Excel spreadsheets? Finally, we have a talk on a Theory of Everything, which will obviously interest everyone!

Returning to the maths: Nic Delcros asks a seemingly trivial question about the number of dimensions of a vector. As any APLer knows, a vector is a list of numbers and, therefore, has 1 dimension, but of course the numbers in a vector nearly always represent a structure of higher dimensionality. Nic takes us on an entertaining exploration of the case where the numbers represent a dynamic event, where one of the dimensions is time – punctuated with beautiful images.

Dieter Kilsch from the University of Applied Sciences (Technische Hochschule) in Bingen obviously enjoys teaching mathematics! In this talk, he actually managed to make me think that I had some insight into why the Irish mathematician William Hamilton invented the Hamiltonian number system (which is populated by Quaternions), and how it allows us to do algebra on points in a 3-dimensional space, similar to the way complex numbers work for 2 dimensions. For example, Quaternions can be used as a tool of thought and computation for image recognition!

Returning to the very real world, Richard Procter is back with an updated talk on “Excel Mining”, following on from his talk at Dyalog ’15 in Sicily. Like many of us, he frequently needs to load data which originates in Microsoft Excel into APL for processing – and sometimes write back to Excel. Richard has tried a variety of different techniques and provides a list of questions that might decide which technique to use in a given scenario (and performance measurements as well).

It should be no big surprise that John Daintree’s big TOE is not something he needs to take a shoe off to demonstrate. Rather, the Theory Of Everything is a unifying idea that might one day replace a large number of system functions, “root methods” and I-Beams which currently allow programmers to ask questions about the Universe that they are running in. The result will hopefully be a system that is more powerful, but simpler and much more self-documenting than the collection of tools that it would replace.

Summary of this week’s videos:

 

Progressive Index-Of

⎕io=0 is assumed throughout.

A recent Forum post motivated investigations into the progressive index-of functions in the FinnAPL Idiom Library:

pix  ← {((⍴⍺)⍴⍋⍋⍺⍳⍺,⍵) ⍳ ((⍴⍵)⍴⍋⍋⍺⍳⍵,⍺)}   ⍝ FinnAPL Idiom 1
pixa ← {((⍋⍺⍳⍺,⍵)⍳⍳⍴⍺) ⍳ ((⍋⍺⍳⍵,⍺)⍳⍳⍴⍵)}   ⍝ FinnAPL Idiom 5

In this note, we:

  • explain what is progressive index-of
  • explain why the two functions work
  • investigate the performance of the two functions
  • provide a more general solution

Progressive Index-Of

Progressive index-of is like index-of () except that each find “uses up” the target of that find. There are no duplicates in the result with the possible exception of ≢⍺ (for “not found”). Thus:

      x←'mississippi'
      y←'dismiss'

      x pix y
11 1 2 0 4 3 5

The following chart illustrates a step-by-step derivation of each progressive index:

0 1 2 3 4 5 6 7 8 9 10

m i s s i s s i p p  i      d i s m i s s
                           11
m i s s i s s i p p  i      d i s m i s s
                           11 1
m i s s i s s i p p  i      d i s m i s s
                           11 1 2
m i s s i s s i p p  i      d i s m i s s
                           11 1 2 0
m i s s i s s i p p  i      d i s m i s s
                           11 1 2 0 4
m i s s i s s i p p  i      d i s m i s s
                           11 1 2 0 4 3
m i s s i s s i p p  i      d i s m i s s
                           11 1 2 0 4 3 5

It is possible to compute the progressive index without looping or recursion, as the two FinnAPL functions demonstrate.

Why It Works

The basic idea of ⍺ pix ⍵ is to substitute for each item of and an equivalent representative, collectively c and d, whence the result obtains as c⍳d. The equivalent representative used here is ranking, specifically the ranking of the indices in .

The ranking of an array is a permutation of order ≢⍵. The smallest major cell is assigned 0; the next smallest is assigned 1; and so on. Ties are resolved by favoring the earlier-occurring cell. The ranking can be computed by ⍋⍋⍵. For example:

      x ⍪ ⍉⍪ ⍋⍋x
m i s s i s  s i p p i
4 0 7 8 1 9 10 2 5 6 3

      y ⍪ ⍉⍪ ⍋⍋y
d i s m i s s
0 1 4 3 2 5 6

⍺ pix ⍵ works on two different rankings of indices in :

⍋⍋⍺⍳⍺,⍵    rankings of indices in of and , favoring
⍋⍋⍺⍳⍵,⍺    rankings of indices in of and , favoring

The first ⍴⍺ items of the former are those for and the first ⍴⍵ of the latter are those for , and we get

pix ← {((⍴⍺)⍴⍋⍋⍺⍳⍺,⍵) ⍳ ((⍴⍵)⍴⍋⍋⍺⍳⍵,⍺)}

The second version depends on the following properties of permutations. Let p be a permutation. Then p[⍋p] ←→ ⍳≢p, the identity permutation, and therefore ⍋p is the inverse of p. Furthermore, p[p⍳⍳≢p] ←→ ⍳≢p and so p⍳⍳≢p is also the inverse of p. The inverse is unique (that’s why it’s called the inverse), therefore ⍋p ←→ p⍳⍳≢p.

      p←97?97         ⍝ a random permutation

      p[⍋p]    ≡ ⍳≢p
1
      p[p⍳⍳≢p] ≡ ⍳≢p
1
      (⍋p)     ≡ p⍳⍳≢p
1

The two rankings are permutations (because the leftmost functions are ) and we just need the first ⍴⍺ items of the former and the first ⍴⍵ items of the latter. Thus:

pixa ← {((⍋⍺⍳⍺,⍵)⍳⍳⍴⍺) ⍳ ((⍋⍺⍳⍵,⍺)⍳⍳⍴⍵)}

Performance

We note that both versions of pix contain the expressions ⍺⍳⍺,⍵ and ⍺⍳⍵,⍺, but the latter is just a rotation of the former. Thus:

pixb ← {i←⍺⍳⍺,⍵ ⋄ ((⍴⍺)⍴⍋⍋i) ⍳ ((⍴⍵)⍴⍋⍋(⍴⍺)⌽i)}
pixc ← {i←⍺⍳⍺,⍵ ⋄ ((⍋i)⍳⍳⍴⍺) ⍳ ((⍋(⍴⍺)⌽i)⍳⍳⍴⍵)}

Which is faster? The answer may surprise.

      x←?1e6⍴3e5
      y←?2e5⍴3e5

      cmpx 'x pixb y' 'x pixc y'
  x pixb y → 9.15E¯2 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  x pixc y → 9.21E¯2 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

A few factors about the Dyalog APL interpreter are relevant to this performance:

  • Computing ⍺⍳⍵,⍺ as a rotation of an already computed i←⍺⍳⍺,⍵ produces a worthwhile speed-up, although only on a relatively small part of the overall computation.
          i←x⍳x,y
          cmpx '(⍴x)⌽i' 'x⍳y,x'
      (⍴x)⌽i → 5.00E¯4 |     0% ⎕⎕                            
      x⍳y,x  → 7.19E¯3 | +1337% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
    
  • Both and have special code for small range data.
          s←?1e6⍴5e5           ⍝ small range
          t←s ⋄ t[t⍳⌈/t]←2e9   ⍝ large range
    
          cmpx 's⍳s' 't⍳t'
      s⍳s → 5.87E¯3 |    0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕                     
      t⍳t → 2.00E¯2 | +240% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
    
          cmpx '⍋s' '⍋t'
      ⍋s → 3.25E¯2 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕     
      ⍋t → 3.84E¯2 | +18% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
    
  • ⍋⍵ has special code when is a permutation.
          p←1e6?1e6           ⍝ p is a permutation
          q←p ⋄ q[999999]←⊃q  ⍝ q is not; both are small-range
    
          cmpx '⍋p' '⍋q'
      ⍋p → 5.81E¯3 |    0% ⎕⎕⎕                           
    * ⍋q → 5.71E¯2 | +882% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
    
  • We saw previously that if p is a permutation then ⍋p ←→ p⍳⍳⍴p. The special code for ⍋p makes the two expressions run at roughly the same speed. The slight advantage for ⍋⍋x versus (⍋x)⍳⍳⍴x would increase if and when ⍋⍋ is recognized as an idiom.
          cmpx '⍋p' 'p⍳⍳⍴p'
      ⍋p    → 6.02E¯3 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕   
      p⍳⍳⍴p → 6.57E¯3 | +9% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
    
          cmpx '⍋⍋x' '(⍋x)⍳⍳⍴x'
      ⍋⍋x      → 3.16E¯2 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕ 
      (⍋x)⍳⍳⍴x → 3.25E¯2 | +2% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
    
    

A General Solution

Index-of works on cells rather than just scalars. Likewise, progressive index-of can also be extended to work on cells. The core algorithm remains the same. The generalization obtains by first reshaping to have the same rank as (having major cells with the same shape), applying the core algorithm, and then reshaping its result to have the same leading shape as the original . Thus:

pixd←{
  m←≢⍺
  r←0⌊1-⍴⍴⍺
  n←×/r↓⍴⍵
  i←⍺⍳⍺⍪(n,1↓⍴⍺)⍴⍵
  (r↓⍴⍵) ⍴ ((⍋i)⍳⍳m) ⍳ ((⍋m⌽i)⍳⍳n)
}

   xx              yy
mmmm            dddd
iiii            iiii
ssss            ssss
ssss            mmmm
iiii            iiii
ssss            ssss
ssss            ssss
iiii     
pppp     
pppp                                  x
iiii                               mississippi

   ⍴xx             ⍴yy                y
11 4            7 4                dismiss

   xx pixd yy                         x pixd y
11 1 2 0 4 3 5                     11 1 2 0 4 3 5

   xx pixd 3 5 4⍴yy                   x pixd 3 5⍴y
11  1  2  0  4                     11  1  2  0  4
 3  5 11  7  6                      3  5 11  7  6
11 10 11 11 11                     11 10 11 11 11

Postscript
After having written the above, I discovered an alternative exposition on progressive index-of by Bob Smith entitled Anatomy of an Idiom. Adám Brudzewsky has produced a Stack Exchange lesson and a Jupyter Notebook based on Smith’s text.

There is also an exposition in J on the same topic, with a more verbose but easier-to-understand derivation.

Is it Sorted?

Motivation

I have been working on the Dyalog APL quicksort implementation. The following programming puzzle arose in the process of doing the QA for this work.

is a simple array. Write a function sorted, without using or , such that sorted ⍵ is 1 if is sorted in ascending order and 0 otherwise.

The point about not using grade is that this is supposed to be an independent check that grade is correct (remains correct) after the new work.

Real Vectors

The simplest case is when is a numeric vector. If furthermore are not complex numbers (a case addressed later), then

   ∧/ 2≤/⍵

each item being less than or equal to the next one, checks that is sorted. Since uses exact comparisons, here we must set ⎕ct←⎕dct←0. Morever, in order that decimal floating-point numbers (DECFs) be compared correctly, here ⎕fr←1287.

Real Arrays

More generally, when is a non-complex numeric matrix, we must check that each row precedes or is equal to the next row. If c and d are consecutive rows, then corresponding items are compared and at the first item where they differ, c[i] must be less than d[i].

   ~ 0 ∊ (2>⌿⍪⍵) ⍲ <\ 2≠⌿⍪⍵

The expression incorporates two refinements:

  • If is not a matrix, first apply ⍪⍵.
  • Instead of checking c[i] is less than d[i], check that c[i] is not greater than d[i]. This finesses the case where c≡d and there is no first item where they differ; that is, the case where <\2≠⌿⍪⍵ is all 0s for that row.

<\on a boolean vector has 0s after the first 1, (and is all 0 if there are no 1s). Therefore, <\2≠⌿⍪⍵ finds the first item (if any) where one cell differs from the next cell, and that item must not be greater than the corresponding item in the next cell.

For example:

   x←?97 3⍴10

   {~ 0 ∊ (2>⌿⍪⍵) ⍲ <\ 2≠⌿⍪⍵} x
0
   {~ 0 ∊ (2>⌿⍪⍵) ⍲ <\ 2≠⌿⍪⍵} x[⍋x;]
1

(Muse: since x above are random numbers, there is a possibility that it is sorted and the first test above can be 1. But: if each elementary particle in the visible universe were a computer and every nanosecond each of them creates a random matrix and tests it for sortedness as above, running from the beginning of the time to the end of our lives, it is still a very safe bet that no 1 would result.)

For integer arrays, there is an alternative of using the signs of the arithmetic difference between successive cells:

   {~ 0 ∊ 1≠t×<\0≠t← × 2-⌿⍪⍵} x[⍋x;]
1

(The sign where consecutive cells first differ must not be 1.) However, computing the difference on floating point numbers can founder on overflow:

   ⊢ x←¯1 1×⌊/⍬
¯1.79769E308 1.79769E308

   {~ 0 ∊ 1≠t×<\0≠t← × 2-⌿⍪⍵} x
DOMAIN ERROR
   {~0∊1≠t×<\0≠t←×2-⌿⍪⍵}x
                   ∧

Complex Numbers

Two complex numbers are ordered first by the real parts and then by the imaginary parts. (This is part of the TAO extension implemented in Dyalog APL version 17.0.) Therefore, a complex array can be tested for sortedness by testing an equivalent real array with each number replaced by their real and imaginary parts, thus:

   (¯1⌽⍳1+⍴⍴⍵) ⍉ 9 11∘.○⍵
   ↑9 11∘○¨⍵
   9 11○⍤1 0⊢⍵

Although the second expression is the shortest, it is less efficient in time, space, and number of getspace calls. The last expression is favored for its brevity and performance.

The number of getspace is a worthwhile measure. Part of the QA process is a rather stringent procedure called the “Shuffle QA”. The entire Shuffle QA takes several weeks to run and its running time is directly related to the number of getspace.

Character Arrays

None of the functions < ≤ ≥ > - × are permitted on characters. This is solved by application of ⎕ucs, converting characters to integers while preserving the ordering.

Putting It All Together

sorted←{
  ⎕ct←⎕dct←0
  ⎕fr←1287
  d←10|⎕dr ⍵
  d∊0 2: ∇ ⎕ucs ⍵
  d=9:   ∇ 9 11○⍤1 0⊢⍵
  ~ 0 ∊ (2>⌿⍪⍵) ⍲ <\ 2≠⌿⍪⍵
}

Other Considerations

That ⍵⌷⍨⊂⍋⍵ is sorted is a necessary but not sufficient condition that ⍋⍵ is correct. For example, an “adversary” can supply the following results for ⍋⍵ so that ⍵⌷⍨⊂⍋⍵ is sorted:

?≢⍵
(≢⍵)⍴?≢⍵
¯1↓⍋⍵
∊ i {⊂⍵[?⍨≢⍵]}⌸⍨ ⍵⌷⍨⊂i←⍋⍵

The last expression randomly permutes the grade indices of equal cells, a result which violates the requirement that grade indices of equal cells are in ascending order. That is, grade must be stable.

In Dyalog APL version 17.0, grade has been extended to work on non-simple arrays, the much discussed TAO, total array ordering. Checking that a non-simple array is sorted without using grade requires facilities discussed in the paper TAO Axioms and is beyond the scope of this note.