4,499
edits
Find: Difference between revisions
Jump to navigation
Jump to search
Add model that reflects common implementation.
(→Empty left argument: Cut "overlay model" discussion: see talk page) |
(Add model that reflects common implementation.) |
||
| Line 1: | Line 1: | ||
{{Built-in|Find|⍷}} is a [[dyadic]] [[primitive function]] which | {{Built-in|Find|⍷}} is a [[dyadic]] [[primitive function]] which indicates where the left [[argument]] appears as a contiguous [[subarray]] of the right argument. | ||
== Examples == | == Examples == | ||
| Line 37: | Line 37: | ||
== Model == | == Model == | ||
Find can be modelled as follows, 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> | ||
<source lang=apl> | <source lang=apl> | ||
ebar←{⎕IO←0 | ebar←{⎕IO←0 | ||
| Line 47: | Line 47: | ||
} | } | ||
</source> | </source> | ||
== Empty left argument == | === Empty left argument === | ||
Implementations differ in their treatment of empty left arguments: | Implementations differ in their treatment of empty left arguments: | ||
* [[APL2]], [[GNU APL]], [[NARS2000]], and [[Dyalog APL]] indicate positions where the left argument can fit, even if the [[prototype]]s don't match. | * [[APL2]], [[GNU APL]], [[NARS2000]], and [[Dyalog APL]] indicate positions where the left argument can fit, even if the [[prototype]]s don't match. | ||
| Line 55: | Line 55: | ||
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]] <source lang=apl inline>∧.=</source> 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 <source lang=apl inline>∧.=</source> 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> | 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]] <source lang=apl inline>∧.=</source> 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 <source lang=apl inline>∧.=</source> 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 <source lang=apl inline>≡</source> with <source lang=apl inline>{(⍺≡⍥⍴⍵)∧(∧/⍺≡¨⍥,⍵)}</source> 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> | |||
<source lang=apl> | |||
ebar2←{⎕IO←0 | |||
r←(≢⍴⍺)⌈≢⍴⍵ ⍝ maximum rank | |||
r>≢⍴⍺:(⍺⍴⍨(⍴⍺),⍨(r-≢⍴⍺)⍴1)∇ ⍵ ⍝ if ⍺ has lesser rank, make it the same rank | |||
(⍴⍺)∨.>r↑(⍴⍵),¯1:(⍴⍵)⍴0 ⍝ return 0s if ⍺ has greater rank or is longer | |||
ww←⍵ | |||
(⍴⍵) ↑ ⍺∘{⍺ {(⍺≡⍥⍴⍵)∧(∧/⍺≡¨⍥,⍵)} (⍴⍺)↑⍵↓ww}¨ ⍳(×⍴⍺)+(⍴⍵)-⍴⍺ | |||
} | |||
</source> | |||
== See also == | == See also == | ||
* [[Membership]] | * [[Membership]] | ||