membership

[Roger|Dyalog]

This used to be a popular parlor game with APL enthusiasts: Suppose the ∊ key is broken on your keyboard. How do you compute membership? To simplify matters a bit, assume that the arguments are integer vectors.

That is, write a function f which does not use ∊, so that:

      x ←  ¯100 + ? 5678 ⍴ 220
      y ← ¯8000 + ? 1234 ⍴ 18000

      (x∊y) ≡ x f y
1

⍳ to the Rescue

      eps ← {(⎕io+≢⍵)>⍵⍳⍺}

      (x∊y) ≡ x eps y
1

This solution has the advantage that ⍳ is optimized so that it would not be much slower than using ∊ directly.

Bit Table

      ⍝
epb←{
  ⎕io←0        
  r←(⌊/,⌈/)⍺,⍵ 
  b←(1+-/⌽r)⍴0 
  b[⍵-⊃r]←1    
  b[⍺-⊃r]      
}              

      (x∊y) ≡ x epb y
1

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.

Outer Product

      epo ← {∨/⍺∘.=⍵}

      (x∊y) ≡ x epo y
1

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

[Bob Armstrong]

Some important words like ' memb have gotten defined rather recently in CoSy , apparently not until Jun,20180627 .

The hard work really is ' match ( around line 1545 in http://cosy.com/4thCoSy/Code/CoSy/CoSy.f ) and making it do the least work .

With that , the rest of the defs are pretty straight forward . Just wanted to mention 2 things . As Roger noted , the simplest way to define ∊ is in terms of ⍳ .

Code: Select all

: where ( L v -- idx ) ' match f? ; 
| Index of first v in list L . count of L if not found . Equivalent to APL ` iota .

What is notable is the use of ' f? which is dyadic ⍳ made into an operator taking a boolean function as an argument .

Code: Select all

: f? ( lst RA boolF -- index )
   | index of first item in LA on which { RA boolF }
   | returns true . Returns LA rho ( bad idea : Returns _n ) if not found . 
   | This is a generalization of APL's dyadic iota , and
   | K's ? both of which are functions which assume the boolF : ' = | 
   >lpstk 2p
    L@ i# 0 ?do L@ i _at R@ lpstk@ execute >_ 
     if lpstkdrop 2P i _i unloop ;then loop
   lpstkdrop L@ rho 2P>  ; 

Then ' memb is simply

Code: Select all

: memb ( L R -- bool ) over >a ['] where 'R ,/ a> rho <i ; 
| Bool of items of R which are in L | See 20180627 

The other comment I wanted to make is that I find a verb built on ' memb , ' venn , very useful :

Code: Select all

: venn  2p (' R@ L@ ~membv LR@ membv LR@ ~membv ') 2P> ; 
| returns list of 3 lists :  ( x nin y ; x in y ; y nin x )