## index-of

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 !

### index-of

In a previous post on Membership, the game was to write a function f which does not use ∊, so that
(x∊y) ≡ x f y for non-empty integer vectors x and y. Here, the game is to write a function f which does not use ⍳, so that:

`      x ←  ¯100 + ? 5678 ⍴ 220      y ← ¯8000 + ? 1234 ⍴ 18000      (x⍳y) ≡ x f y1`

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

Outer Product

`      io ← {+/∧\⍵∘.≠⍺}      (x⍳y) ≡ x io y1`

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

Index Table

`      ⍝it←{  r←(⌊/,⌈/)⍺,⍵  i←(1+-/⌽r)⍴≢⍺  i[⌽⍺-⊃r]←⌽⍳≢⍺  i[ ⍵-⊃r]}      (x∊y) ≡ x it y1`

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

The 1+ in the expression b←(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.

A variant of it without the two ⌽ in the indexed assignment computes the index of the last occurrence. (⍳ and it compute the index of the first occurrence.)

Interval Index

`      ⍝iv←{  x←{⍵[⍋⍵]}⍺  b←1,2≠/x  u←b/x  i←0⌈u⍸⍵  ((≢⍺)×~c)+(b/⍋⍺)[i]×c←⍵=u[i]}      (x∊y) ≡ x iv y1`

This solution is O(n×⍟n). Some notes about its implementation:

• Indices returned by ⍸ need to be mapped to the corresponding indices required by ⍳.
• In such mapping, indices for items of ⍵ less than ⌊/⍺, in the range (⌊/,⌈/) of ⍺ but not in ⍺, and greater than ⌈/⍺, need to be handled. That mapping is effected by the computations involving c.
• b can be computed as ≠x, but ≠⍵ is available only in Dyalog APL version 18.0 or later. Moreover, ≠x is less independent of ⍳ than 1,2≠/x.
• u can be computed as ∪x, but ∪ is less independent of ⍳ than b/x.
• x←{⍵[⍋⍵]}⍺ and ⍋⍺ can be replaced by x←⍺[i←⍋⍺]. The two computations are equally fast because {⍵[⍋⍵]} is an idiom.

Relaxed Requirements

It is known that the implementation of ⍳ has many special cases. (You can see this for yourself by running some benchmarks.) ⍳ on integer vector arguments is a special case, different from the special cases of ⍳ on arguments with k-byte (k≠4) major cells and ⍳ on floating point vectors. The following solutions do not use ⍳ on integer vectors.

`      ik ← {(⍺,⍪⍺)⍳(⍵,⍪⍵)}      if ← {(⍺+0.5)⍳(⍵+0.5)}      (x⍳y) ≡ x ik y1      (x⍳y) ≡ x if y1`
Roger|Dyalog

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