Outer Product: Difference between revisions

From APL Wiki
Jump to navigation Jump to search
m (remove reference to matrix multiplication, that should be for Inner Product instead)
Line 1: Line 1:
{{Built-in|Outer Product|<nowiki>∘.</nowiki>}}, or '''Table''' is a [[monadic operator]], which will produce a [[dyadic function]] when applied with a [[dyadic function]]. In APL, the outer product is a generalisation of the [https://en.wikipedia.org/wiki/Matrix_multiplication matrix product], which allows not only multiplication, but any [[dyadic function]] given. In short, outer product allows you to apply a given function on each element of the left array with each element of the right array. Basically, a shortcut for constructing nested [https://en.wikipedia.org/wiki/For_loop for loop]s.
{{Built-in|Outer Product|<nowiki>∘.</nowiki>}}, or '''Table''' is a [[monadic operator]], which will produce a [[dyadic function]] when applied with a [[dyadic function]]. In short, outer product allows you to apply a given function on each element of the left array with each element of the right array. Basically, a shortcut for constructing nested [https://en.wikipedia.org/wiki/For_loop for loop]s.


=== Syntax ===
=== Syntax ===
Line 18: Line 18:
│3 4│3 5│3 6│
│3 4│3 5│3 6│
└───┴───┴───┘
└───┴───┴───┘
      x ∘.× y ⍝ matrix multiplication
4  5  6
8 10 12
12 15 18


       ⍝ works for multi-dimensional arrays as well
       ⍝ works for multi-dimensional arrays as well

Revision as of 02:14, 6 September 2021

∘.

Outer Product (∘.), or Table is a monadic operator, which will produce a dyadic function when applied with a dyadic function. In short, outer product allows you to apply a given function on each element of the left array with each element of the right array. Basically, a shortcut for constructing nested for loops.

Syntax

By right, a monadic operator should be a single glyph, and the operand should be on the left. However, for historical reasons, the outer product operator is not only a bi-glyph denoted as ∘., the operand also appears on the right instead.

Notably, this syntactical inconsistency is resolved in J and BQN, where the outer product operator, called Table, and denoted / and respectively, abide by the usual operator syntax.

Examples

      x  1 2 3
      y  4 5 6
      x ∘., y ⍝ visualizing outer product
┌───┬───┬───┐
1 41 51 6
├───┼───┼───┤
2 42 52 6
├───┼───┼───┤
3 43 53 6
└───┴───┴───┘

      ⍝ works for multi-dimensional arrays as well
      y2 3  'abcdef'
      x2 2  4
      x∘.,y 
┌───┬───┬───┐
1 a1 b1 c
├───┼───┼───┤
1 d1 e1 f
└───┴───┴───┘
┌───┬───┬───┐
2 a2 b2 c
├───┼───┼───┤
2 d2 e2 f
└───┴───┴───┘
             
┌───┬───┬───┐
3 a3 b3 c
├───┼───┼───┤
3 d3 e3 f
└───┴───┴───┘
┌───┬───┬───┐
4 a4 b4 c
├───┼───┼───┤
4 d4 e4 f
└───┴───┴───┘

Applications

Outer product is useful for solving problems that intuitively requires a polynomial time algorithm. However, this also indicates that such an algorithm might not be the fastest solution.

For example, suppose we want to find duplicated elements in an non-nested array. Intuitively speaking, the easiest way to solve this problem is to compare each element of the array with all other elements, which is exactly what an outer product does.

      x  1 2 3 2
        matrix  x∘.=x ⍝ compare elements with each other using equal
1 0 0 0
0 1 0 1
0 0 1 0
0 1 0 1
        count  +/matrix ⍝ get the number of occurence of each element
1 2 1 2
        indices  count  2 ⍝ get the indices of elements which occured more than once
0 1 0 1
        duplicated   indices/x 
2

      ((+/x∘.=x)2)/x ⍝ everything above in one line
2
      (⊢∪⍤/⍨2(+/∘.=)) x ⍝ point-free/tacit version
2

Using similar techniques, we can define a function that generates prime numbers by using an outer product of Residue.

     primes  {x1↓⍳  (2>+0=x∘.|x)/x}
     primes 10
2 3 5 7
      primes 20
2 3 5 7 11 13 17 19

Again, using outer product might not yield the fastest solution. There are faster solutions such as Sieve of Eratosthenes.

External links

Documentation


APL built-ins [edit]
Primitive functions
Scalar
Monadic ConjugateNegateSignumReciprocalMagnitudeExponentialNatural LogarithmFloorCeilingFactorialNotPi TimesRollTypeImaginarySquare Root
Dyadic AddSubtractTimesDivideResiduePowerLogarithmMinimumMaximumBinomialComparison functionsBoolean functions (And, Or, Nand, Nor) ∙ GCDLCMCircularComplexRoot
Non-Scalar
Structural ShapeReshapeTallyDepthRavelEnlistTableCatenateReverseRotateTransposeRazeMixSplitEncloseNestCut (K)PairLinkPartitioned EnclosePartition
Selection FirstPickTakeDropUniqueIdentitySelectReplicateExpandSet functions (IntersectionUnionWithout) ∙ Bracket indexingIndex
Selector Index generatorGradeIndex OfInterval IndexIndicesDeal
Computational MatchNot MatchMembershipFindNub SieveEncodeDecodeMatrix InverseMatrix DivideFormatExecuteMaterialiseRange
Primitive operators Monadic EachCommuteConstantReplicateExpandReduceWindowed ReduceScanOuter ProductKeyI-BeamSpawnFunction axis
Dyadic BindCompositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner ProductPowerAtUnderRankDepthVariantStencilCut (J)
Quad names
Arrays Index originMigration levelAtomic vector
Functions Name classCase convertUnicode convert
Operators SearchReplace