4,494
edits
Find: Difference between revisions
Jump to navigation
Jump to search
m
Text replacement - "<source" to "<syntaxhighlight"
(Add model that reflects common implementation.) |
m (Text replacement - "<source" to "<syntaxhighlight") Tags: Mobile edit Mobile web edit |
||
| (One intermediate revision by the same user not shown) | |||
| Line 5: | Line 5: | ||
Both arguments can be arrays of any [[shape]]. The entire left argument is tested against each position in the right argument. The result is a [[boolean]] array having the same shape as the right argument, where a 1 indicates the position of the [[first]] element of the matched subarray (which can be seen as the "leftmost" or "top left" position in case of a [[vector]] or [[matrix]]). If the left argument has lower [[rank]], it is treated as if the shape is prepended with ones. If the left argument has higher rank, Find does not error, but it is never found in the right argument (resulting in an all-zero array). | Both arguments can be arrays of any [[shape]]. The entire left argument is tested against each position in the right argument. The result is a [[boolean]] array having the same shape as the right argument, where a 1 indicates the position of the [[first]] element of the matched subarray (which can be seen as the "leftmost" or "top left" position in case of a [[vector]] or [[matrix]]). If the left argument has lower [[rank]], it is treated as if the shape is prepended with ones. If the left argument has higher rank, Find does not error, but it is never found in the right argument (resulting in an all-zero array). | ||
< | <syntaxhighlight lang=apl> | ||
'ANA'⍷'BANANA' ⍝ Matches may overlap | 'ANA'⍷'BANANA' ⍝ Matches may overlap | ||
0 1 0 1 0 0 | 0 1 0 1 0 0 | ||
| Line 27: | Line 27: | ||
WEEK⍷'DAY' ⍝ WEEK not found in 'DAY'; left arg may have higher rank but it is never found | WEEK⍷'DAY' ⍝ WEEK not found in 'DAY'; left arg may have higher rank but it is never found | ||
0 0 0 | 0 0 0 | ||
</ | </syntaxhighlight> | ||
For [[nested array|nested arrays]], Find tests for exact [[match]] between the elements. | For [[nested array|nested arrays]], Find tests for exact [[match]] between the elements. | ||
< | <syntaxhighlight lang=apl> | ||
'BIRDS' 'NEST'⍷'BIRDS' 'NEST' 'SOUP' | 'BIRDS' 'NEST'⍷'BIRDS' 'NEST' 'SOUP' | ||
1 0 0 | 1 0 0 | ||
</ | </syntaxhighlight> | ||
== Model == | == Model == | ||
Find can be modelled as follows (for non-empty left arguments), where all possible subarrays of the right argument are checked to see if they [[match]] the left argument:<ref>[[Roger Hui|Hui, Roger]]. [https://forums.dyalog.com/viewtopic.php?f=30&t=1735 ⍷ follies]. Dyalog Forums. 16 Feb 2021.</ref> | Find can be modelled as follows (for non-empty left arguments), where all possible subarrays of the right argument are checked to see if they [[match]] the left argument:<ref>[[Roger Hui|Hui, Roger]]. [https://forums.dyalog.com/viewtopic.php?f=30&t=1735 ⍷ follies]. Dyalog Forums. 16 Feb 2021.</ref> | ||
< | <syntaxhighlight lang=apl> | ||
ebar←{⎕IO←0 | ebar←{⎕IO←0 | ||
r←(≢⍴⍺)⌈≢⍴⍵ ⍝ maximum rank | r←(≢⍴⍺)⌈≢⍴⍵ ⍝ maximum rank | ||
| Line 46: | Line 46: | ||
(⍴⍵) ↑ ⍺∘{⍺≡(⍴⍺)↑⍵↓ww}¨ ⍳(×⍴⍺)+(⍴⍵)-⍴⍺ | (⍴⍵) ↑ ⍺∘{⍺≡(⍴⍺)↑⍵↓ww}¨ ⍳(×⍴⍺)+(⍴⍵)-⍴⍺ | ||
} | } | ||
</ | </syntaxhighlight> | ||
=== Empty left argument === | === Empty left argument === | ||
Implementations differ in their treatment of empty left arguments: | Implementations differ in their treatment of empty left arguments: | ||
| Line 53: | Line 53: | ||
* [[APL+]] finds empty arrays everywhere, even where they would extend beyond the edges of the right argument. | * [[APL+]] finds empty arrays everywhere, even where they would extend beyond the edges of the right argument. | ||
The prototype is never used, in contrast to [[Match]], which in many APLs compares prototypes of empty arrays. The behavior may come from the use of the [[inner product]] < | The prototype is never used, in contrast to [[Match]], which in many APLs compares prototypes of empty arrays. The behavior may come from the use of the [[inner product]] <syntaxhighlight lang=apl inline>∧.=</syntaxhighlight> in early [[Array_model#Flat_array_theory|flat]] APLs where [[Match]] is not a primitive; this function naturally checks elements and not the prototype. [[Adin Falkoff]] presented code for Find-like functions using <syntaxhighlight lang=apl inline>∧.=</syntaxhighlight> at [[APL79]].<ref>[[Adin Falkoff|Falkoff, Adin]]. [https://dl.acm.org/doi/10.1145/390009.804448 A note on pattern matching: Where do you find the match to an empty array?] at [[APL79]].</ref> | ||
Correspondingly, the above model can be amended to match the behaviour of the primitive (in APL2, etc.) by replacing the < | Correspondingly, the above model can be amended to match the behaviour of the primitive (in APL2, etc.) by replacing the <syntaxhighlight lang=apl inline>≡</syntaxhighlight> with <syntaxhighlight lang=apl inline>{(⍺≡⍥⍴⍵)∧(∧/⍺≡¨⍥,⍵)}</syntaxhighlight> which ignores prototypes, only comparing shape and elements:<ref>[[Adám Brudzewsky|Brudzewsky, Adám]]. [https://forums.dyalog.com/viewtopic.php?f=30&t=1735&p=7416#p7416 RE: ⍷ follies]. Dyalog Forums. 23 Aug 2022.</ref> | ||
< | <syntaxhighlight lang=apl> | ||
ebar2←{⎕IO←0 | ebar2←{⎕IO←0 | ||
r←(≢⍴⍺)⌈≢⍴⍵ ⍝ maximum rank | r←(≢⍴⍺)⌈≢⍴⍵ ⍝ maximum rank | ||
| Line 64: | Line 64: | ||
(⍴⍵) ↑ ⍺∘{⍺ {(⍺≡⍥⍴⍵)∧(∧/⍺≡¨⍥,⍵)} (⍴⍺)↑⍵↓ww}¨ ⍳(×⍴⍺)+(⍴⍵)-⍴⍺ | (⍴⍵) ↑ ⍺∘{⍺ {(⍺≡⍥⍴⍵)∧(∧/⍺≡¨⍥,⍵)} (⍴⍺)↑⍵↓ww}¨ ⍳(×⍴⍺)+(⍴⍵)-⍴⍺ | ||
} | } | ||
</ | </syntaxhighlight> | ||
== See also == | == See also == | ||
* [[Membership]] | * [[Membership]] | ||