Outer Product: Difference between revisions

Jump to navigation Jump to search
mNo edit summary
(11 intermediate revisions by 3 users not shown)
Line 1: Line 1:
== Outer Product ==
{{Built-in|Outer Product|<nowiki>∘.</nowiki>}}, or '''Table''' is a [[monadic operator]], which will produce a [[dyadic function]] when applied with a [[dyadic function]]. Outer product applies the [[operand]] function on each [[element]] of the left array with each element of the right array. It can be described as a shortcut for constructing nested [[wikipedia:for loop|for loop]]s.
Outer product 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.


=== Syntax ===
=== Syntax ===
By right, a [[monadic operator]] should be a monograph (i.e. consist of only one character), and the operand should be on the left. However, due to [[legacy reason]], the outer product operator is not only a [[diagraph]] denoted as <source lang=apl inline>∘.</source>, the operand also appears on the right instead.
Outer Product differs from all other [[monadic operator]]s, which are written as a single [[glyph]], with the operand on the left. For [[backwards compatibility|historical reasons]], the outer product operator is a [[bi-glyph]] denoted as <source lang=apl inline>∘.</source>, and its appears on the right. This special notation is derived from the <source lang=apl inline>f.g</source> notation of [[inner product]]:<ref>[[Adin Falkoff|Falkoff, A.D.]] and [[Ken Iverson|K.E. Iverson]]. [https://www.jsoftware.com/papers/APL360TerminalSystem1.htm#ip The APL\360 Terminal System: Inner and Outer Products]. Research Report RC-1922. [[IBM]] Watson Research Center. 1967-10-16.</ref>
<blockquote>
The result of an inner product is an array with rank two less than the sum of the argument ranks. The result of an outer product, on the other hand, is always an array of rank equal to the sum of the argument ranks. This follows from the fact that the reduction operation, which collapses two dimensions in an inner product, is not used in the outer product. The notation for outer product reflects this by canonically using a small circle as the first symbol. Thus, the ordinary outer product is written as <code>a∘.×b</code> .
</blockquote>


Notably, this syntactical inconsistency is resolved in [[BQN]], where the outer product operator <source lang=bqn inline>⌜</source> abides with the usual operator syntax. Also note that it is called table in BQN.
This syntactical inconsistency is resolved in [[J]] and [[BQN]], where the outer product operator, called Table, and denoted <source lang=j inline>/</source> and <code>⌜</code> respectively, has the usual operator syntax.


=== Examples ===
=== Examples ===
Line 19: Line 21:
│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 array as well
       ⍝ works for multi-dimensional arrays as well
       y←2 3 ⍴ 'abcdef'
       y←2 3 ⍴ 'abcdef'
       x←2 2 ⍴ ⍳4
       x←2 2 ⍴ ⍳4
Line 53: Line 51:


=== Applications ===
=== Applications ===
Outer product is useful for solving problems that intuitively requires a [https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time polynomial time] algorithm.  
Outer product is useful for solving problems that intuitively require a [[wikipedia:Time_complexity#Polynomial_time|polynomial time]] algorithm. This may also indicate that such an algorithm is not the fastest solution.
However, this also indicates that such 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.
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.
Line 72: Line 69:


       ∪((+/x∘.=x)≥2)/x ⍝ everything above in one line
       ∪((+/x∘.=x)≥2)/x ⍝ everything above in one line
2     (∪((2≤(+/∘.=⍨))(/⍨⍨)⊢)) x ⍝ point-free/tacit version
2
      (⊢∪⍤/⍨2≤(+/∘.=⍨)) x ⍝ point-free/tacit version
2
2
</source>
</source>
''Note: due to [[function-operator overloading]]'', to use [[replicate]] in a [[fork]], we have to use the workaround <source lang=apl inline>/⍨⍨</source>.
Using similar techniques, we can define a function that generates prime numbers by using an outer product of [[Residue]].
 
Using similar techniques, we can define a function that generate prime numbers by using an outer product of [[Residue]].
<source lang=apl>
<source lang=apl>
     primes ← {x←1↓⍳⍵ ⋄ (2>+⌿0=x∘.|x)/x}
     primes ← {x←1↓⍳⍵ ⋄ (2>+⌿0=x∘.|x)/x}
Line 84: Line 80:
       primes 20
       primes 20
2 3 5 7 11 13 17 19
2 3 5 7 11 13 17 19
</source>
</source>
Again, using outer product might not yield the fastest solution. There are faster solutions such as [https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes Sieve of Eratosthenes].
Here there are faster solutions such as the [[wikipedia:Sieve of Eratosthenes|Sieve of Eratosthenes]].
== External links ==
 
* [https://mlochbaum.github.io/OuterProduct/ Outer Product as an Introduction to APL and a Pretty Cool Thing in General]: website for LambdaConf talk by [[Marshall Lochbaum]]
 
=== Documentation ===
 
* [https://help.dyalog.com/latest/#Language/Primitive%20Operators/Outer%20Product.htm Dyalog]
* [https://microapl.com/apl_help/ch_020_020_890.htm APLX]
* J [https://www.jsoftware.com/help/dictionary/d420.htm Dictionary], [https://code.jsoftware.com/wiki/Vocabulary/slash#dyadic NuVoc]
* [https://mlochbaum.github.io/BQN/doc/map.html#table BQN]
 
== References ==
<references/>
{{APL built-ins}}[[Category:Primitive operators]]

Navigation menu