Find

From APL Wiki
Revision as of 14:02, 23 August 2022 by Marshall (talk | contribs) (→‎Empty left argument: Cut "overlay model" discussion: see talk page)
Jump to navigation Jump to search

Find (⍷) is a dyadic primitive function which tests if the left argument appears as a contiguous subarray of the right argument.

Examples

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). 

      'ANA'⍷'BANANA'  ⍝ Matches may overlap
0 1 0 1 0 0

      WEEK
SUNDAY
MONDAY
TUESDAY
WEDNESDAY
THURSDAY
FRIDAY
SATURDAY
      'DAY'⍷WEEK  ⍝ Find the pattern 'DAY' in WEEK; right arg may have higher rank
0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0
0 0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0
      WEEK⍷'DAY'  ⍝ WEEK not found in 'DAY'; left arg may have higher rank but it is never found
0 0 0

For nested arrays, Find tests for exact match between the elements. 

      'BIRDS' 'NEST'⍷'BIRDS' 'NEST' 'SOUP'
1 0 0

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:[1] 

ebar←{⎕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}¨ ⍳(×⍴⍺)+(⍴⍵)-⍴⍺
}

Empty left argument

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 prototypes don't match.
  • APLX never finds any empty arrays.
  • 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 ∧.= in early 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 ∧.= at APL79.[2]

See also

External links

Documentation

References

  1. ↑ Hui, Roger. ⍷ follies. Dyalog Forums. 16 Feb 2021.
  2. ↑ Falkoff, Adin. A note on pattern matching: Where do you find the match to an empty array? at APL79.
APL built-ins [edit]
Primitives (Timeline) Functions
Scalar
Monadic Conjugate ∙ Negate ∙ Signum ∙ Reciprocal ∙ Magnitude ∙ Exponential ∙ Natural Logarithm ∙ Floor ∙ Ceiling ∙ Factorial ∙ Not ∙ Pi Times ∙ Roll ∙ Type ∙ Imaginary ∙ Square Root ∙ Round
Dyadic Add ∙ Subtract ∙ Times ∙ Divide ∙ Residue ∙ Power ∙ Logarithm ∙ Minimum ∙ Maximum ∙ Binomial ∙ Comparison functions ∙ Boolean functions (And, Or, Nand, Nor) ∙ GCD ∙ LCM ∙ Circular ∙ Complex ∙ Root
Non-Scalar
Structural Shape ∙ Reshape ∙ Tally ∙ Depth ∙ Ravel ∙ Enlist ∙ Table ∙ Catenate ∙ Reverse ∙ Rotate ∙ Transpose ∙ Raze ∙ Mix ∙ Split ∙ Enclose ∙ Nest ∙ Cut (K) ∙ Pair ∙ Link ∙ Partitioned Enclose ∙ Partition
Selection First ∙ Pick ∙ Take ∙ Drop ∙ Unique ∙ Identity ∙ Stop ∙ Select ∙ Replicate ∙ Expand ∙ Set functions (Intersection ∙ Union ∙ Without) ∙ Bracket indexing ∙ Index ∙ Cartesian Product ∙ Sort
Selector Index generator ∙ Grade ∙ Index Of ∙ Interval Index ∙ Indices ∙ Deal ∙ Prefix and suffix vectors
Computational Match ∙ Not Match ∙ Membership ∙ Find ∙ Nub Sieve ∙ Encode ∙ Decode ∙ Matrix Inverse ∙ Matrix Divide ∙ Format ∙ Execute ∙ Materialise ∙ Range
Operators Monadic Each ∙ Commute ∙ Constant ∙ Replicate ∙ Expand ∙ Reduce ∙ Windowed Reduce ∙ Scan ∙ Outer Product ∙ Key ∙ I-Beam ∙ Spawn ∙ Function axis ∙ Identity (Null, Ident)
Dyadic Bind ∙ Compositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner Product ∙ Determinant ∙ Power ∙ At ∙ Under ∙ Rank ∙ Depth ∙ Variant ∙ Stencil ∙ Cut ∙ Direct definition (operator) ∙ Identity (Lev, Dex)
Quad names Index origin ∙ Comparison tolerance ∙ Migration level ∙ Atomic vector
Retrieved from ‘https://aplwiki.com/index.php?title=Find&oldid=9021’