## membership

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 !

### membership

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 y1`

⍳ to the Rescue

`      eps ← {(⎕io+≢⍵)>⍵⍳⍺}      (x∊y) ≡ x eps y1`

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 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.

Outer Product

`      epo ← {∨/⍺∘.=⍵}      (x∊y) ≡ x epo y1`

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

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

### Re: membership

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 ) `

Bob Armstrong

Posts: 19
Joined: Wed Dec 23, 2009 8:41 pm
Location: 39.038681° -105.079070° 2500m