Outer Product: Difference between revisions

From APL Wiki
Jump to navigation Jump to search
mNo edit summary
mNo edit summary
Line 1: Line 1:
== Outer Product ==
== Outer Product ==
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 for each element from the left array with each element to the right array.
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.
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.


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

Revision as of 09:44, 5 September 2021

Outer Product

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 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 for loops.

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 ∘., the operand also appears on the right instead.

Notably, this syntactical inconsistency is resolved in BQN, where the outer product operator abides with the usual operator syntax. Also note that it is called table in BQN.

Examples

      x ← 1 2 3
      y ← 4 5 6
      x ∘., y ⍝ visualizing outer product
┌───┬───┬───┐
│1 4│1 5│1 6│
├───┼───┼───┤
│2 4│2 5│2 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
      y←2 3 ⍴ 'abcdef'
      x←2 2 ⍴ ⍳4
      x∘.,y 
┌───┬───┬───┐
│1 a│1 b│1 c│
├───┼───┼───┤
│1 d│1 e│1 f│
└───┴───┴───┘
┌───┬───┬───┐
│2 a│2 b│2 c│
├───┼───┼───┤
│2 d│2 e│2 f│
└───┴───┴───┘
             
┌───┬───┬───┐
│3 a│3 b│3 c│
├───┼───┼───┤
│3 d│3 e│3 f│
└───┴───┴───┘
┌───┬───┬───┐
│4 a│4 b│4 c│
├───┼───┼───┤
│4 d│4 e│4 f│
└───┴───┴───┘

Applications

Outer product is useful for solving problems that intuitively requires a polynomial time algorithm. 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.

      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

Note: due to function-operator overloading, to use replicate in a fork, we have to use the workaround /⍨⍨.

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

     primes ← {x←1↓⍳⍵ ⋄ (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.