Operator each-nub

[StephenTaylor]

CPU cycles are often cheaper than development time. APL programs are prone to overcompute.

      q←⍎¨V←40⍴ '2+2' '+/⍳1E7'

Let's execute each unique element only once.

      q≡{(⍎¨⍵)[⍵⍳⍺]}∘∪⍨ V
1
      EEN←{(⍎¨⍵)[⍵⍳⍺]}∘∪⍨ ⍝ fn: execute each nub
      q≡EEN V
1

Execute is one function: an operator would make the technique useful for others.

      q≡⍎{(⍺⍺¨⍵)[⍵⍳⍺]}∘∪⍨ V
1
      EN←{(⍺⍺¨⍵)[⍵⍳⍺]}∘∪⍨ ⍝ op: each-nub
SYNTAX ERROR
      EN←{(⍺⍺¨⍵)[⍵⍳⍺]}∘∪⍨ ⍝ op: each-nub
     ∧

Oops. Compose will take a function as left-operand (⍎{(⍺⍺¨⍵)[⍵⍳⍺]}) but not an operator. A wrapper removes the difficulty.

      EN←{⍺⍺{(⍺⍺¨⍵)[⍵⍳⍺]}∘∪⍨⍵} ⍝ op: each-nub
      q≡⍎EN V
1

It seems a pity to use the wrapper. Can it be elided?

Stephen

PS Functionistas might prefer to lose the index brackets. Perhaps that looks better because the ⍺⍺s aren't juxtaposed.

      EN←{⍺⍺{(⍵⍳⍺)⊃¨⊂⍺⍺¨⍵}∘∪⍨⍵} ⍝ op: each-nub
      q≡⍎EN V 
1

SJT

[Roger|Dyalog]

      EN←{(⊂t⍳⍵)⌷⍺⍺¨t←∪⍵} ⍝ op: each-nub

      v←40⍴'2+2' '+/⍳10000000'
      (⍎¨v) ≡ ⍎EN v
1

Ken Iverson discussed this problem in his Programming Style in APL http://www.jsoftware.com/papers/APLStyle.htm, 1978, in the subsection entitled "Functions on subsets".

[Roger|Dyalog]

You can avoid the local assignment to t by using one of them new-fangled trains.

      EN ← {(∪⍵) ((⊂⍳)⌷(⍺⍺¨⊣)) ⍵}
      (⍎¨v) ≡ ⍎EN v
1

The fork has ⌷ as the middle tine; the left tine (⊂⍳) and right tine (⍺⍺¨⊣) are both atops.

[Phil Last]

SNAP!

      eu←{
     (⊂u⍳⍵)⌷⍺⍺¨u←∪⍵
     ⍵ ⍺⍺¨{(⊂⍵⍳⍺)⌷⍺⍺ ⍵}∪⍵ ⍝ assignment free alternative
⍝ each unique
 }

[Roger|Dyalog]

Also in Notation as a Tool of Thought, http://www.jsoftware.com/papers/tot.htm, 1980 (Turing Award lecture), Section 4.3 Summarization and Distribution.

Ken Iverson discussed this problem in his Programming Style in APL http://www.jsoftware.com/papers/APLStyle.htm, 1978, in the subsection entitled "Functions on subsets".

[Roger|Dyalog]

(∪⍵)⍳⍵, index in nub, is an interesting computation.

Suppose ⍵ is a vector of 4-byte integers (⎕dr is 323), let's say ?1e6⍴2e9. Can you compute index in nub faster than (∪⍵)⍳⍵? There is an alternative faster expression in Dyalog 13.2, and if ⍳ is as fast as it can be (in a future Dyalog version) then the alternative expression is faster by a factor of about 2.

Answer in http://www.jsoftware.com/jwiki/Essays/Index_in_Nub. The expressions translate pretty directly into Dyalog.

[JohnS|Dyalog]

Nice.

{(⍎¨⍵)[⍵⍳⍺]}∘∪⍨ ⍝ fn: execute each nub
...
Execute is one function: an operator would make the technique useful for others.
...
It seems a pity to use the wrapper. Can it be elided?

For V14, we did experiment with "Monadic Operator Expressions" (MOXs), which were arbitrary derived function expressions with exactly one operand missing somewhere in the tree. But they turned out to be rather complex beasties, so they're back on the rainy-day list. Given MOXs, we could have transformed Stephen's expression:

      {(⍎¨⍵)[⍵⍳⍺]}∘∪⍨
→     {(⊂⍵⍳⍺)⌷⍎¨⍵}∘∪⍨          ⍝ [squad-indexing / bracket-indexing]
→     {(⊂⍺⍳⍨⍵)⌷⍎¨⍵}∘∪⍨         ⍝ switching ⍳'s args
→     {(⍺(⊂⍳⍨)⍵)⌷⍎¨⍵}∘∪⍨       ⍝ ⊂ atop ⍳⍨
→     {(⍺(⊂⍳⍨)⍵)⌷⍺⊢∘(⍎¨)⍵}∘∪⍨  ⍝ dyadic ⍎¨ ignores left arg
→     ((⊂⍳⍨)⌷⊢∘(⍎¨))∘∪⍨        ⍝ dfn → fork
→     ((⊂⍳⍨)⌷⊢∘( ¨))∘∪⍨        ⍝ removing ⍎: derived function → MOX

Beware of bugs in the above code; I have only proved it correct, not tried it. - D.E.Knuth