membership
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 !
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 !
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 "off-by-1" 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 "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: 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: 26
- 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: No registered users and 1 guest
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group