membership
Forum rules
This forum is for discussing APLrelated issues. If you think that the subject is offtopic, then the Chat forum is probably a better place for your thoughts !
This forum is for discussing APLrelated issues. If you think that the subject is offtopic, then the Chat forum is probably a better place for your thoughts !
2 posts
• Page 1 of 1
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:
⍳ to the Rescue
This solution has the advantage that ⍳ is optimized so that it would not be much slower than using ∊ directly.
Bit Table
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 "offby1" pitfalls waiting to trap the unwary.
Outer Product
This solution has the advantage of being rock solid, but the disadvantage of being O(n*2).
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 "offby1" 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).
 RogerDyalog
 Posts: 238
 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 ⍳ .
What is notable is the use of ' f? which is dyadic ⍳ made into an operator taking a boolean function as an argument .
Then ' memb is simply
The other comment I wanted to make is that I find a verb built on ' memb , ' venn , very useful :
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
2 posts
• Page 1 of 1
Who is online
Users browsing this forum: Phil Last and 1 guest
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group