## interval index

APL-related discussions - a stream of APL consciousness.
Not sure where to start a discussion ? Here's the place to be
Forum rules
This forum is for discussing APL-related issues. If you think that the subject is off-topic, then the Chat forum is probably a better place for your thoughts !

### interval index

In previous posts, Membership and Index-Of, the game was to write functions f and g such that

`      (x∊y) ≡ x f y      (x⍳y) ≡ x g y`

for non-empty integer vectors x and y, where f does not use ∊ and g does not use ⍳. Here, the game is to write a function h which does not use ⍸, so that for non-empty integer vectors x and y:

`      x ←  {⍵[⍋⍵]} ¯100 + ? 5678 ⍴ 220      y ←          ¯200 + ? 1234 ⍴ 440      (x⍸y) ≡ x h y1`

⎕io←0 is assumed. ⎕io delenda est!

Outer Product

`      ivo ← {¯1++/⍵∘.≥⍺}      (x⍸y) ≡ x ivo y1`

This solution has the advantage of being rock solid, but the disadvantage of being O(n*2).

If the arguments were floating point numbers, ⎕ct←0 would be necessary because ⍸ is defined on exact comparisons.

Index Table

`      ⍝ivt←{  r←(⌊/,⌈/)⍺  i←(1+-/⌽r)⍴0  i[⍺-⊃r]+←1  i←¯1++\i  (b×i[0⌈(⍵⌊⊃⌽r)-⊃r])-~b←⍵≥⊃r}      (x⍸y) ≡ x ivt y1`

This solution is blown out of the water if the range of values in ⍺ is large. Otherwise, it's pretty fast.

The 1+ in the expression i←(1+-/⌽r)⍴0 is an instance of the famous "off-by-1" pitfalls waiting to trap the unwary. One of my beefs with ⎕io is that it introduces opportunities for making an off-by-1 error where there was none.

`      ivg ← {¯1+(≢⍺)↓i⊣i[i]←+\(≢⍺)>i←⍋⍺⍪⍵}      (x⍸y) ≡ x ivg y1`

This solution is O(n) because ⍋ is O(n).

The algorithm first appeared as the function "classify" in §1.2 of Some Uses of { and }, 1987 and also in §14 of A History of APL in 50 Functions, 2016.

The unusual construct i⊣i[i]←blah can be made expressed in another way. Since i, being the result of ⍋, is (am?) a permutation, i⊣i[i]←⍳≢i is equivalent to ⍋i. That is, i[i]←blah assigns the items in the order ⍋i and is equivalent to blah[⍋i]. Therefore, ivg is equivalent to ivg1 (although ivg is a bit faster):

`      ivg1 ← {¯1+(≢⍺)↓(+\i<≢⍺)[⍋i←⍋⍺⍪⍵]}      (x⍸y) ≡ x ivg1 y1`
Roger|Dyalog

Posts: 236
Joined: Thu Jul 28, 2011 10:53 am