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

Postby Roger|Dyalog on Thu Apr 15, 2021 7:17 pm

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).
Roger|Dyalog
 
Posts: 231
Joined: Thu Jul 28, 2011 10:53 am

Re: membership

Postby Bob Armstrong on Mon Apr 19, 2021 12:13 am

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 )
User avatar
Bob Armstrong
 
Posts: 19
Joined: Wed Dec 23, 2009 8:41 pm
Location: 39.038681° -105.079070° 2500m


Return to APL Chat

Who is online

Users browsing this forum: No registered users and 1 guest